Example 1: min heap in c++
priority_queue <int, vector<int>, greater<int>> minHeap;
Example 2: min max heap java
// min heap: PriorityQueue implementation from the JDK
PriorityQueue<Integer> prq = new PriorityQueue<>();
// max heap: PriorityQueue implementation WITH CUSTOM COMPARATOR PASSED
// Method 1: Using Collections (recommended)
PriorityQueue<Integer> prq = new PriorityQueue<>(Collections.reverseOrder());
// Method 2: Using Lambda function (may cause Integer Overflow)
PriorityQueue<Integer> prq = new PriorityQueue<>((a, b) -> b - a);
Example 3: heaps in java
public class BinaryHeap {
private static final int d= 2;
private int[] heap;
private int heapSize;
/**
* This will initialize our heap with default size.
*/
public BinaryHeap(int capacity){
heapSize = 0;
heap = new int[ capacity+1];
Arrays.fill(heap, -1);
}
/**
* This will check if the heap is empty or not
* Complexity: O(1)
*/
public boolean isEmpty(){
return heapSize==0;
}
/**
* This will check if the heap is full or not
* Complexity: O(1)
*/
public boolean isFull(){
return heapSize == heap.length;
}
private int parent(int i){
return (i-1)/d;
}
private int kthChild(int i,int k){
return d*i +k;
}
/**
* This will insert new element in to heap
* Complexity: O(log N)
* As worst case scenario, we need to traverse till the root
*/
public void insert(int x){
if(isFull())
throw new NoSuchElementException("Heap is full, No space to insert new element");
heap[heapSize++] = x;
heapifyUp(heapSize-1);
}
/**
* This will delete element at index x
* Complexity: O(log N)
*
*/
public int delete(int x){
if(isEmpty())
throw new NoSuchElementException("Heap is empty, No element to delete");
int key = heap[x];
heap[x] = heap[heapSize -1];
heapSize--;
heapifyDown(x);
return key;
}
/**
* This method used to maintain the heap property while inserting an element.
*
*/
private void heapifyUp(int i) {
int temp = heap[i];
while(i>0 && temp > heap[parent(i)]){
heap[i] = heap[parent(i)];
i = parent(i);
}
heap[i] = temp;
}
/**
* This method used to maintain the heap property while deleting an element.
*
*/
private void heapifyDown(int i){
int child;
int temp = heap[i];
while(kthChild(i, 1) < heapSize){
child = maxChild(i);
if(temp < heap[child]){ heap[i] = heap[child]; }else break; i = child; } heap[i] = temp; } private int maxChild(int i) { int leftChild = kthChild(i, 1); int rightChild = kthChild(i, 2); return heap[leftChild]>heap[rightChild]?leftChild:rightChild;
}
/**
* This method used to print all element of the heap
*
*/
public void printHeap()
{
System.out.print("nHeap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
/**
* This method returns the max element of the heap.
* complexity: O(1)
*/
public int findMax(){
if(isEmpty())
throw new NoSuchElementException("Heap is empty.");
return heap[0];
}
public static void main(String[] args){
BinaryHeap maxHeap = new BinaryHeap(10);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.delete(5);
maxHeap.printHeap();
}
}
Example 4: max heap c++
#include <iostream>
using namespace std;
void max_heap(int *a, int m, int n) {
int j, t;
t = a[m];
j = 2 * m;
while (j <= n) {
if (j < n && a[j+1] > a[j])
j = j + 1;
if (t > a[j])
break;
else if (t <= a[j]) {
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j/2] = t;
return;
}
void build_maxheap(int *a,int n) {
int k;
for(k = n/2; k >= 1; k--) {
max_heap(a,k,n);
}
}
int main() {
int n, i;
cout<<"enter no of elements of array\n";
cin>>n;
int a[30];
for (i = 1; i <= n; i++) {
cout<<"enter elements"<<" "<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
cout<<"Max Heap\n";
for (i = 1; i <= n; i++) {
cout<<a[i]<<endl;
}
}
Example 5: heap sort heapify and max heap in binary tree
Implementation of heap sort in C:
#include <stdio.h>
int main()
{
int heap[10], array_size, i, j, c, root, temporary;
printf("\n Enter size of array to be sorted :");
scanf("%d", &array_size);
printf("\n Enter the elements of array : ");
for (i = 0; i < array_size; i++)
scanf("%d", &heap[i]);
for (i = 1; i < array_size; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{ // if child is greater than parent swap them
temporary = heap[root]; // as structure is of complete binary tree
heap[root] = heap[c]; // it took logn steps to reach from root to leaf
heap[c] = temporary;
}
c = root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < array_size; i++)
printf("%d\t ", heap[i]); //printing the heap array
for (j = array_size - 1; j >= 0; j--)
{
temporary = heap[0];
heap[0] = heap[j] ; /* swap max element with rightmost leaf element */
heap[j] = temporary;
root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
{
temporary = heap[root];
heap[root] = heap[c];
heap[c] = temporary;
}
root = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < array_size; i++)
printf("\t %d", heap[i]);
}
Example 6: example of a min heap
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40