Heap As Priority Queue

↞↞Previous ↞Heap Data Structure

Heap As Priority Queue

This part of tutorial is in continuation of previous post. Before reading this part I would highly recommend to go through first part(Heap Data Structure) of this tutorial.

What is Priority Queue
Many important applications require selection of an item of the highest priority among a dynamically changing set of items. A priority queue is an Abstract Data Type that offer the needs of such applications. For an example- Priority queues may be used for task scheduling in computers, where higher priority task runs first that lower priority tasks. Priority queue also used in some important algorithms of Graph like Prim’s algorithm and Dijkstra’s algorithm.

A priority queue offers methods that allow:

  • get an item of highest priority
  • removal an item with the highest priority
  • inserting an item
  • change an item

I already covered basics of Heap in details in my previous section. Let’s directly jump to the heap as priority queue. Here the heap will be represented in such a way that it will support all the above mentioned Priority queue methods. Here we will also see the TopDown or trickleUp heap construction algorithm.

Let’s discuss each method in detail:
Remember array representation of a heap to understand the code.
insertKey() & trickleUp()
This is another method to create a Heap. It Is not as efficient as maxHeapify().
When you insert a key to the Heap, you always insert at the last position of the array. There may be the case that newly inserted key violate the Heap condition. Call trickleUp() to place this key at proper position. In trickleUp() you compare the new key to its parent – if the parent is smaller, swap the key with parent key. Repeat the process until you reach to the root(top) or the heap condition satisfied for this key. The running time of this method is O(logn), since the path traced from the insertion position to the root has length O(logn).

Top element of the array is the highest element. This method return first element. It takes O(1) time.

This method removes the largest element which is always at the top of array. First it gets the A[0] element – then it copies the A[n] to A[0] – now there may be the case that A[0] element violate the heap condition – call maxHeapify(0) to top element. This method takes O(logn) time since it works on the top root element and may move top to bottom equals to the height of the tree i.e O(logn).
This method change key at particular position. There are two possibilities here, either the changed key will be greater than the current key or it will be smaller than the current key. If it is greater then there may be the chance that it is greater than its parent , use trickleUp() to place it at proper position. If the changed key is smaller the current key, there may be the chance that that it is smaller than its children, use maxHeapify() to place it at proper position. This method running time is also proportional to its height i.e. O(logn).

Next  ↠Questions on Heap ↠↠