↞↞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.
import java.util.Arrays;
public class Heap {
private int[] heapArray;
private int maxSize;
private int heapSize;
public Heap(int size) {
heapSize = 0;
maxSize = size;
heapArray = new int[maxSize];
}
public boolean isEmpty() {
return heapSize == 0;
}
//insert at last position, if parent is smaller then swap
//with parent. Repeat the process until key is at its proper
//position.
public void insertKey(int key) {
assert heapSize > maxSize-1 : "heap overflow";
heapArray[heapSize] = key;
trickleUp(heapSize++);
}
private void trickleUp(int i) {
int parent = (i - 1) / 2;
while (i > 0 && heapArray[i] > heapArray[parent]) {
int temp = heapArray[parent];
heapArray[parent] = heapArray[i];
heapArray[i] = temp;
i = parent;
parent = (i - 1) / 2;
}
}
public int peek() {
assert heapSize <= 0 : "heap underflow";
return heapArray[0];
}
public int extractMax() {
assert heapSize <= 0 : "heap underflow";
int max = heapArray[0];
heapArray[0] = heapArray[--heapSize];
maxHeapify(0);
return max;
}
public void changeKey(int i, int key) {
int oldValue = heapArray[i];
heapArray[i] = key;
if(key > oldValue){
trickleUp(i);
}else{
maxHeapify(i);
}
}
public void maxHeapify(int i) {
int largest = i;
while (largest < heapSize/2) {
int left = (2 * i) + 1;
int right = left + 1;
if (left < heapSize && heapArray[left] > heapArray[i]) {
largest = left; // largest=6
}
if (right < heapSize && heapArray[right] > heapArray[largest]) {
largest = right;
}
if (largest != i) {
int temp = heapArray[i];
heapArray[i] = heapArray[largest];
heapArray[largest] = temp;
i = largest;
} else {
break;
}
}
}
public void showHeap() {
for (int i = 0; i < heapSize; i++) {
System.out.print(heapArray[i] + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int[] A1 = { 1, 8, 9, 2, 10, 14, 3, 4, 7, 16 };
System.out.println("Original Array:: "+Arrays.toString(A1));
Heap heap = new Heap(10);
for (int i : A1) {
heap.insertKey(i);
}
System.out.print("After inserting to heap:: ");
heap.showHeap();
System.out.println();
System.out.println("Removed Max:: " + heap.extractMax());
System.out.println("Removed Max:: " + heap.extractMax());
System.out.print("After two removal the heap:: ");
heap.showHeap();
System.out.println();
heap.insertKey(50);
heap.insertKey(0);
System.out.print("After inserting 50 and 0 the heap:: ");
heap.showHeap();
}
}
Output
--------
Original Array:: [1, 8, 9, 2, 10, 14, 3, 4, 7, 16]
After inserting to heap:: 16, 14, 10, 7, 9, 8, 3, 1, 4, 2
Removed Max:: 16
Removed Max:: 14
After two removal the heap:: 10, 9, 8, 7, 2, 4, 3, 1,
After inserting 50 and 0 the heap:: 50, 10, 8, 9, 2, 4, 3, 1, 7, 0
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).
peek()
Top element of the array is the highest element. This method return first element. It takes O(1) time.
extracMax()
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).
changeKey()
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).
Leave a Reply