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;
}

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.