1132. Data Structure - Heap
Max Heap and Min Heap


Implement heap with array.

1. Heap

1.1 Definition of Heap

A heap is a binary tree with these characteristics:

  • It’s complete. This means it’s completely filled in, reading from left to right across each row, although the last row need not be full.
  • It’s (usually) implemented as an array. Binary trees can be stored in arrays, rather than using references to connect the nodes.
  • Each node in a heap satisfies the heap condition, which states that every node’s key is larger/smaller than the keys of its children.

image

1.2 Types of Heap

  • Max Heap - The value of each node is less than the value of its parent, with the maximum-value element at the root.
  • Min Heap - The value of each node is greater than the value of its parent, with the minimum-value element at the root.

1.3 Common Operations on Heap

  • Insertion - Insert a new value to heap.
  • Removal - Remove and return the root.
  • Get - Get the value of root.

1.4 Time Complexity

  • Insertion - $O(\log{}n)$
  • Removal - $O(\log{}n)$
  • Get - $O(1)$

1.5 Efficiency of Heap Operations

A heap is a special kind of binary tree, the number of levels L in a binary tree equals $\log_{2}(N+1)$, where N is the number of nodes. The bubble up and bubble down routines cycle through their loops L-1 times, so the first takes time proportional to $\log_{2}N$, and the second somewhat more because of the extra comparison. Thus, the heap operations we’ve talked about here all operate in $O(\log{}N)$ time.

1.6 Elements Sequence

If you remove a node and then insert the same node, the result is not necessarily the restoration of the original heap. A given set of nodes can be arranged in many valid heaps, depending on the order in which nodes are inserted.

2. Heap Implementation

2.1 Array Heap

Heap can be implemented with array. A heap is a complete binary tree implies that there are no “holes” in the array used to represent it. The traversal method use to achieve array representation is Level Order. image

2.2 Index Relationship

For a node at index i in the array,

  • Its parent is (i - 1) / 2.
  • Its left child is 2 * i + 1.
  • Its right child is 2 * i + 2.

3. Max Heap

A max-heap is a complete binary tree where each node is larger than its children. The root, therefore, is the maximum element in the heap.

3.1 Insertion

Insertion means add new element to the heap. Initially, the new element is placed in the first open position at the end of the array. Insertion increases the array size by one. Here are the steps for adding the new element to max heap:

  • 1) Add new node to bottom, rightmost.
  • 2) Compare the value of this node with its parent. If value of parent is less than child, then swap them.
  • 3) Repeat step 2) to bubble up this new node to maintain the heap condition if possible; otherwise, stop.

image

3.2 Removal

Removal means removing the node with the maximum key. This node is always the root. Removing decreases the array size by one. Here are the steps for removing the maximum node:

  • 1) Remove the root node.
  • 2) Move the last element(bottom, rightmost) to root.
  • 3) Compare the value of this child with its parent. If value of parent is less than child, then swap them.
  • 4) Repeat step 3) to bubble down this node to maintain the heap condition if possible; otherwise, stop.

image

3.3 Implementing MaxHeap

The following code is the implementation of max heap with type integer.

public class MaxHeap {
    private int capacity = 10;
    protected Integer[] array;
    protected int size;

    public MaxHeap () {
        array = new Integer[capacity];
        size = 0;
    }

    public MaxHeap (int capacity) {
        this.capacity = capacity;
        array = new Integer[capacity];
        size = 0;
    }

    // add new element into heap
    public void add(int value) {
        if (size >= array.length - 1) {
            array = this.resize();
        }

        // place element into heap at bottom (right most)
        array[size] = value;
        size++;

        bubbleUp();
    }

    // bubble up the last node with it's parent until they are in the order of max heap
    protected void bubbleUp() {
        int index = this.size - 1;  // last node (right most)

        while (hasParent(index) && (parent(index) < array[index])) {
            // parent and child are out of order; swap them
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }


    // remove and return the maximum element in the heap
    public int remove() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        // get the root, which is the maximum value
        int result = peek();

        // move the last leaf to root
        array[0] = array[size - 1];
        array[size - 1] = null;
        size--;

        bubbleDown();

        return result;
    }

    // bubble down the new root to proper position to maintain the order of max heap
    protected void bubbleDown() {
        // root
        int index = 0;

        // heap is complete tree, so it's safe to check left child first
        while (hasLeftChild(index)) {
            int biggerChild = leftIndex(index);

            // find the smaller child
            if (hasRightChild(index)
                && array[leftIndex(index)] < (array[rightIndex(index)])) {
                biggerChild = rightIndex(index);
            }

            if (array[index] > array[biggerChild]) {
                break;
            } else {
                // parent and child are out of order; swap them
                swap(index, biggerChild);
                index = biggerChild;
            }
        }
    }

    // get the root without removing it from heap
    public int peek() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }

        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    protected boolean hasParent(int i) {
        return i > 0;
    }

    protected int leftIndex(int i) {
        return 2 * i + 1;
    }

    protected int rightIndex(int i) {
        return 2 * i + 2;
    }

    protected boolean hasLeftChild(int i) {
        return leftIndex(i) <= size - 1;
    }

    protected boolean hasRightChild(int i) {
        return rightIndex(i) <= size - 1;
    }

    protected int parent(int i) {
        return array[parentIndex(i)];
    }

    protected int parentIndex(int i) {
        return (i - 1) / 2;
    }

    protected Integer[] resize() {
        return Arrays.copyOf(array, array.length * 2);
    }

    protected void swap(int index1, int index2) {
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }
}

4. Min Heap

A min-heap is a complete binary tree where each node is smaller than its children. The root, therefore, is the minimum element in the heap.

4.1 Implementing MinHeap

The following code is the implementation of max heap with type integer. The only difference with max heap is the comparison.

public class MinHeap {
    private int capacity = 10;
    protected Integer[] array;
    protected int size;

    public MinHeap () {
        array = new Integer[capacity];
        size = 0;
    }

    public MinHeap (int capacity) {
        this.capacity = capacity;
        array = new Integer[capacity];
        size = 0;
    }

    // add new element into heap
    public void add(int value) {
        if (size >= array.length - 1) {
            array = this.resize();
        }

        // place element into heap at bottom (right most)
        array[size] = value;
        size++;

        bubbleUp();
    }

    // bubble up the last node with it's parent until they are in the order of max heap
    protected void bubbleUp() {
        int index = this.size - 1;  // last node (right most)

        while (hasParent(index) && (parent(index) > array[index])) {
            // parent and child are out of order; swap them
            swap(index, parentIndex(index));
            index = parentIndex(index);
        }
    }


    // remove and return the maximum element in the heap
    public int remove() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        // get the root, which is the maximum value
        int result = peek();

        // move the last leaf to root
        array[0] = array[size - 1];
        array[size - 1] = null;
        size--;

        bubbleDown();

        return result;
    }

    // bubble down the new root to proper position to maintain the order of max heap
    protected void bubbleDown() {
        // root
        int index = 0;

        // heap is complete tree, so it's safe to check left child first
        while (hasLeftChild(index)) {
            int biggerChild = leftIndex(index);

            // find the smaller child
            if (hasRightChild(index)
                && array[leftIndex(index)] > (array[rightIndex(index)])) {
                biggerChild = rightIndex(index);
            }

            if (array[index] < array[biggerChild]) {
                break;
            } else {
                // parent and child are out of order; swap them
                swap(index, biggerChild);
                index = biggerChild;
            }
        }
    }

    // get the root without removing it from heap
    public int peek() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }

        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    protected boolean hasParent(int i) {
        return i > 0;
    }

    protected int leftIndex(int i) {
        return 2 * i + 1;
    }

    protected int rightIndex(int i) {
        return 2 * i + 2;
    }

    protected boolean hasLeftChild(int i) {
        return leftIndex(i) <= size - 1;
    }

    protected boolean hasRightChild(int i) {
        return rightIndex(i) <= size - 1;
    }

    protected int parent(int i) {
        return array[parentIndex(i)];
    }

    protected int parentIndex(int i) {
        return (i - 1) / 2;
    }

    protected Integer[] resize() {
        return Arrays.copyOf(array, array.length * 2);
    }

    protected void swap(int index1, int index2) {
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }
}

5. Heap Sort

Construct a heap with all numbers, and delete root one by one to get the sorted list.

6. Priority Queue

Priority queues are useful for any application that involves processing elements based on some priority.

Priority Queue vs Heap
A priority queue can be implemented using many of the data structures(Array, Linked List, or Binary Search Tree). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we’ll use a new data structure called a heap.

Priority Queue vs TreeMap

  • PriorityQueue Allows Duplicate(i.e with same priority) while TreeMap doesn’t.
  • Complexity of PriorityQueue is O(n)(when is increases its size), while that of TreeMap is O(logn)(as it is based on Red Black Tree)
  • PriorityQueue is based on Array while in TreeMap nodes are linked to each other, so contains method of PriorityQueue would take O(n) time while TreeMap would take O(logn) time.

6.1 Common Operations on Priority Queue

  • Add - Insert a new value to priority queue.
  • Poll - Remove and return the maximum/minimum.
  • Peek - Get the maximum/minimum.

6.2 Time Complexity

  • Add - $O(\log{}n)$
  • Poll - $O(\log{}n)$
  • Peek - $O(1)$

6.3 Max Priority Queue

public class PriorityQueueMax {
    private MaxHeap heap;

    public PriorityQueueMax() {
        heap = new MaxHeap();
    }

    public PriorityQueueMax(int capacity) {
        heap = new MaxHeap(capacity);
    }

    public void add(int val) {
        heap.add(val);
    }

    public int poll() {
        return heap.remove();
    }

    public int peek() {
        return heap.peek();
    }

    public boolean isEmpty() {
        return heap.size == 0;
    }

    public int size() {
        return heap.size;
    }
}

6.4 Min Priority Queue

public class PriorityQueueMin {
    private MinHeap heap;

    public PriorityQueueMin() {
        heap = new MinHeap();
    }

    public PriorityQueueMin(int capacity) {
        heap = new MinHeap(capacity);
    }

    public void add(int val) {
        heap.add(val);
    }

    public int poll() {
        return heap.remove();
    }

    public int peek() {
        return heap.peek();
    }

    public boolean isEmpty() {
        return heap.size == 0;
    }

    public int size() {
        return heap.size;
    }
}

7. Classic Problems

8. Source Files

9. Reference