FANDOM


Heap is a tree-based data structure that satisfies the heap property: for each parent-child pair, the key (value) of parent is ordered with respect to key of the child. Heaps are an implementation of abstract data structure called priority queue. In fact, priority queues are also called heaps.

A heap can be classified into: Max-heap and Min-heap.

  1. In Max-heap, for each parent-child pair, the value of parent is greater than the value of child.
  2. In Min-heap, for each parent-child pair, the value of child is greater than the value of parent.

Algorithm Edit

The code for heapsort and kth-smallest element in C++ is presented below:

include <bits/stdc++.h>
using namespace std;
void heapify(vector<int> &v, int idx, int n)
{
     /* make sure that parent node is larger than both children and if it is not then perform swapping */
     int left = 2*idx;
     int right = 2*idx+1;
     int largest=idx;
     if(left < n && v[left] > v[idx])
          largest = left;
     if(right < n && v[right] > v[largest])
          largest = right;
     if(largest != idx)
     {
          swap(v[idx], v[largest]);
          heapify(v, largest, n);
     }
}

void buildHeap(vector<int> &v, int n) { for(int i = n/2 - 1; i >= 0; --i) heapify(v, i, n); }
void heapsort(vector<int> &v, int n)
{
     buildHeap(v, n);
     for(int i = n-1; i >= 0; --i)
     {
          swap(v[0], v[i]);
          heapify(v, 0, i);
     }
}

int kthsmallest(vector<int> &v, int k) { /* return kth smallest element in collection for valid k>=1 */ int n = v.size(); vector<int> a(v.begin(), v.begin() + k); buildHeap(a, k); for(int i = k; i < n; ++i) { if(v[i] < a[0]) { a[0] = v[i]; heapify(a, 0, k); } } return a[0]; }
int main()
{
     /* Testing our kthsmallest and heapsort implementation */
     vector<int> v;
     vector<int>::iterator it;
     int n,p,q,r;
     cin>>n;
     for(int i=0;i<n;++i)
     {
          cin>>p;
          v.push_back(p);
     }
     for(int i=1;i<=n;i++)cout<<kthsmallest(v,i)<<endl;
     heapsort(v,n);
     for(it=v.begin();it!=v.end();it++)
     {
          cout<<*it<<endl;
     }
     return 0;
}