A heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, the value of I is less than or equal to the values of its children.

Max Heap Example

Building a Max Heap

To build a max heap, start with an unsorted array and adjust it to satisfy the heap property. The largest element will be at the root.


import java.util.Arrays;

class MaxHeap {
    private int[] Heap;
    private int size;
    private int maxsize;

    public MaxHeap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MAX_VALUE;
    }

    private int parent(int pos) { return pos / 2; }

    private void swap(int fpos, int spos) {
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

    public void insert(int element) {
        Heap[++size] = element;
        int current = size;

        while (Heap[current] > Heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
  
    public static void main(String[] arg) {
        MaxHeap maxHeap = new MaxHeap(15);
        maxHeap.insert(5);
        maxHeap.insert(3);
        maxHeap.insert(17);
        maxHeap.insert(10);
        maxHeap.insert(84);
        maxHeap.insert(19);
        maxHeap.insert(6);
        maxHeap.insert(22);
        maxHeap.insert(9);
        System.out.println(Arrays.toString(maxHeap.Heap));
    }
}

Console Output:

[2147483647, 84, 22, 19, 9, 10, 17, 5, 6, 3]

Min Heap Example

Building a Min Heap

In a min heap, the smallest element is at the root. The heap property is maintained such that each parent node is less than or equal to its child nodes.


import java.util.Arrays;

class MinHeap {
    private int[] Heap;
    private int size;
    private int maxsize;

    public MinHeap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MIN_VALUE;
    }

    private int parent(int pos) { return pos / 2; }

    private void swap(int fpos, int spos) {
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

    public void insert(int element) {
        Heap[++size] = element;
        int current = size;

        while (Heap[current] < Heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
  
    public static void main(String[] arg) {
        MinHeap minHeap = new MinHeap(15);
        minHeap.insert(5);
        minHeap.insert(3);
        minHeap.insert(17);
        minHeap.insert(10);
        minHeap.insert(84);
        minHeap.insert(19);
        minHeap.insert(6);
        minHeap.insert(22);
        minHeap.insert(9);
        System.out.println(Arrays.toString(minHeap.Heap));
    }
}

Console Output:

[-2147483648, 3, 5, 6, 9, 84, 19, 17, 22, 10]

Heap Sort Example

Using Heap for Sorting

Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max heap and then repeatedly extracts the maximum element.


import java.util.Arrays;

class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;
  
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
  
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
  
    void heapify(int arr[], int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
  
        if (left < n && arr[left] > arr[largest])
            largest = left;
  
        if (right < n && arr[right] > arr[largest])
            largest = right;
  
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
  
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        HeapSort hs = new HeapSort();
        hs.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Console Output:

[5, 6, 7, 11, 12, 13]

Heapify Process Example

Understanding Heapify

Heapify is a process of converting a binary tree into a heap. It ensures that the subtree rooted at the given node satisfies the heap property.


import java.util.Arrays;

class HeapifyExample {
    void heapify(int arr[], int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
  
        if (left < n && arr[left] > arr[largest])
            largest = left;
  
        if (right < n && arr[right] > arr[largest])
            largest = right;
  
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
  
    public static void main(String args[]) {
        int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
        HeapifyExample he = new HeapifyExample();
        he.heapify(arr, arr.length, 0);
        System.out.println(Arrays.toString(arr));
    }
}

Console Output:

[9, 7, 5, 3, 1, 2, 4, 6, 8, 0]

Priority Queue Using Heap

Implementing Priority Queue

A priority queue can be efficiently implemented using a heap. Elements are dequeued in order of priority, which is determined by their value in the heap.


import java.util.PriorityQueue;

class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue<>();
        pq.add(10);
        pq.add(20);
        pq.add(15);
  
        System.out.println(pq.poll()); // Outputs 10
        System.out.println(pq.poll()); // Outputs 15
        System.out.println(pq.poll()); // Outputs 20
    }
}

Console Output:

10 15 20