[ACE] Priority Queue and Heap

Priority Queue and Heap

---

• A priority queue stores a collection of entries
• Each entry is a pair (key, value)
• A heap is a binary tree storing key-value pairs at its nodes and satisfying the following properties:
• Heap-Order: for every internal node v other than the root key(v) >= key(parent(v))
• It is a complete binary tree

Motivation

We have three ways to implement priority queue

• unsorted list (O(1) for insert but O(n) for removeMin() and min())
• sorted list (O(n) for insert but O(1) for removeMin())
• Heap(Explain later)

We want to find a data structure which can optimize priority queue operation to be better than O(n).
Then, we find heap, which gives us O(logn) due to the usage of binary tree.

The difference between priority queue and Maps(HashMaps)?

Both have key and values.
Two distinct entries in a priority queue can have the same key.
But in hashmap, the key should be different.
Is it a reason why PQ doesnt have find(key)?
Why?
It is because in priority queue, we need to know(explore) the order of every element(entry)? [e.g. Student grades]
But by using hashtable or maps we just need a data structure to store things?

Operations on heap

Insertion into a Heap

The insertion algorithm consists of three steps:

• Find the insertion algorithm consists of three steps
• Store k at z

• Restore the heap-order property–UpHeap

  @Override
  public void insert(int elem) {
      heap[++size] = elem;
      upHeap(size);
  }
  private void upHeap(int pos) {
      while(heap[pos] < heap[parent(pos)]){
          swap(pos, parent(pos));
          pos = parent(pos);
      }
  }
  

Upheap terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k
Since a heap has height O(log n), upheap runs in O(log n) time

Removal from a heap

The removal algorithm consists of three steps:

• Replace the root key with the key of the last node w
• Remove w

• Restore the heap-order property–DownHeap

      @Override
      public int removeMin() {
          int temp = heap[1];
          swap(1, size);
          heap[size] = 0;
          size--;
          if(size != 0){
              downHeap(1);
          }
          return temp;
      }
      private void downHeap(int start) {
      if(size >= 3){
          int temp = (heap[leftChild(start)]>heap[rightChild(start)])? rightChild(start):leftChild(start);
          while(heap[start] > heap[temp]){
              swap(start, temp);
              if(!isExternalNode(temp)){
                  start = temp;
              }
          }
      }else if(size == 2){
          if(heap[start] > heap[leftChild(start)]){
              swap(start, leftChild(start));
          }
      }
  }
  

Downheap terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k
Since a heap has height O(log n), downheap runs in O(log n ) time

Implement Priority Queue with a Heap

You need to let all the operations in PriorityQueue become operations in Heap

And the element(entry) in the queue(or generic) should be comparable, which will need you to implement Comparable interface and implement compareTo() method

The result is as follows:

After we learn heap, we can working on a sort which has O(n log n)time –Heap Sort