Design a Heap[OOD]

Implement PriorityQueue (a.k.a Heap)

• Heap is a (binary) tree logically, is Array storage
• Across the entire tree, the relation between a parent node and a child node stays consistent.

  Example: min heap

1. the parent node is always <= its two child nodes (parent node is the smallest node in the subtree rooted at itself).

2. the relation between the two child nodes can differ.

• The common implementation of a heap is using a complete binary tree.

• A complete binary  tree" is a binary tree in which every level, except possibly the last level,  is completely filled, and all nodes are as far left as possible.

Index of cur = i, what is the index of the two child nodes?

• left child of Index i = 2 * i  + 1
• right child of Index i = 2 * i + 2
• parent of Index i = (i -1) / 2
• the root of the tree Is at index 0

Basic Heap Internal Operations

1

/        \

                  2           10

I   \      I          \

5        3      13   19

I     \      /  \

       11     8    6  4

 

public class MinHeap { // Capacity Limited MinHeap

// fields

private int[] array;

// methods

percolateUp(index)

percolateDown(index)

offer():

4

/        \

2               10

I   \      I          \

5        3      13   19

I     \      /  \

       11     8    6  

{1, 2,  10, 5, 3, 13,  19,  11, 8, 6, 4}
1+ log2 + log3 + …. logn

poll():

update();

Heapify():

convert an array into a heap in O(n) time

  2 → 11
       /         \
   3              4
/       \         /     \
10        8    7         6
        /    \     
     13   14       

13 11 4 10 8 7 6 2 3

            4 → 11
       /         \
   8              6
/       \         /     \
2        11    7         13
        /    \     
     10      3   

k = logn

2^0 * k-1 + 2^1 * (k-2) + 2^2 * (k-3) + 2^(k-2) * 1 = Sum

2^1 * k-1 + 2^2 * (k - 2) + 2^3 * (k-3) + …. 2^(k-1) * 2  = 2Sum  

k-1 + 2 + 2^2 + …. 2^(k-2) + 2^(k-1) = 2^k → 2logn → n

public class MinHeap { // Capacity Limited MinHeap

// fields

private int[] array;

private int size;

// methods

public MinHeap(int cap) {

   if (cap <= 0) {

     throw new IllegalArgumentException("capacity can not be <= 0");

   }

   array = new int[cap];

   size = 0;

 }

 public MinHeap(int[] array) {

   if (array == null || array.length == 0) {

     throw new IllegalArgumentException("input array can not be null or empty");

   }

   this.array = array;

   size = array.length;

   heapify();

 }

peek();

          private void heapify() {

   for (int i = size / 2 - 1; i >= 0; i--) { (size - 2) / 2

     percolateDown(i);

   }

 }

public void offer(int ele) { [0, size)

   if (size == array.length) {

     int[] newArray = new int[(int) (array.length * 1.5)];

     copy(array, newArray); // deep copy → for loop, clone();

     array = newArray;

   }

   array[size] = ele;

   percolateUp(size);

   size++;

 }

public int poll() throws Exception {

   if (size == 0) {

     throw new NoSuchElementException("heap is empty");

   }

   int result = array[0];

   array[0] = array[size - 1];

   size--;

   percolateDown(0);

   return result;

}

// return the original value.

 public int update(int index, int ele) {

   if (index < 0 || index > size - 1) {

     throw new ArrayIndexOutOfBoundException("invalid index range");

   }

   int result = array[index];

   array[index] = ele;

   if (result > ele) {

     percolateUp(index);

   } else {

     percolateDown(index);

   }

   return result;

 }

private void percolateUp(int index) {

   while (index > 0) {

     int parentIndex = (index - 1) / 2;

     if (array[parentIndex] > array[index]) {

       swap(array, parentIndex, index);

     } else {

       break;

     }

     index = parentIndex;

   }

 }

private void percolateDown(int index) {

   // corner case

   while (index <= (size - 2) / 2) { // the last non-leaf node index

     int leftChildIndex = index * 2 + 1;

     int rightChildIndex = index * 2 + 2;

     int swapCandidate = leftChildIndex; // smallest one among leftchild and

                                         // rightchild.

     // update swapCandidate if rightchild exists and it is smaller than

     // leftChild.

     if (rightChildIndex <= size - 1 && array[leftChildIndex] >= array[rightChildIndex]) {

       swapCandidate = rightChildIndex;

     }

     // swap if necessary.

     if (array[index] > array[swapCandidate]) {

       swap(array, index, swapCandidate);

     } else {

       break;

     }

     index = swapCandidate;

   }

}