binary heaps

Binary Heaps :-

Introduction :-

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: • 

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. • the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.    

In a heap the highest (or lowest) priority element is always stored at the root, hence the name "heap". A heap is not a sorted structure and can be regarded as partially ordered. As you see from the picture, there is no particular relationship among nodes on any given level, even among the siblings. 

Since a heap is a complete binary tree, it has a smallest possible height - a heap with N nodes always has O(log N) height. 

A heap is useful data structure when you need to remove the object with the highest (or lowest) priority. A common use of a heap is to implement a priority queue. 

Array Implementation A complete binary tree can be uniquely represented by storing its level order traversal in an array. 

 

The root is the second item in the array. We skip the index zero cell of the array for the convenience of implementation. Consider k-th element of the array, the 

its left child is located at 2*k index  its right child is located at 2*k+1. index  its parent is located at k/2 index  

Insert The new element is initially appended to the end of the heap (as the last element of the array). The heap property is repaired by comparing the added element with its parent and moving the added element up a level (swapping positions with the parent). This process is called "percolation up". The comparison is repeated until the parent is larger than or equal to the percolating element. 

  

The following code example demonstrates the algorithm 

public void insert(Comparable x) {  if(size == heap.length - 1) doubleSize();  

 //Insert a new item to the end of the array  int pos = ++size;  

 //Percolate up  for(; pos > 1 && x.compareTo(heap[pos/2]) < 0; pos = pos/2 )   heap[pos] = heap[pos/2];  

 heap[pos] = x; }  

The worst-case runtime of the algorithm is O(log n), since we need at most one swap on each level of a heap on the path from the inserted node to the root. 

DeleteMin The minimum element can be found at the root, which is the first element of the array. We remove the root and replace it with the last element of the heap and then restore the heap property by percolating down. Similar to insertion, the worst-case runtime is O{log n).  

HeapSort The algorithm runs in two steps. Given an array of data, first, we build a heap and then turn it into a sorted list by calling deleteMin. The running time of the algorithm is O(n log n). 

Priority Queue 

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

A priority queue is different from a "normal" queue, because instead of being a "first-in-firstout" data structure, values come out in order by priority. A priority queue might be used, for example, to handle the jobs sent to the Computer Science Department's printer: Jobs sent by the department chair should be printed first, then jobs sent by professors, then those sent by graduate students, and finally those sent by undergraduates. The values put into the priority queue would be the priority of the sender (e.g., using 4 for the chair, 3 for professors, 2 for grad students, and 1 for undergrads), and the associated information would be the document to print. Each time the printer is free, the job with the highest priority would be removed from the 

print queue, and printed. (Note that it is OK to have multiple jobs with the same priority; if there is more than one job with the same highest priority when the printer is free, then any one of them can be selected.) 

The operations that need to be provided for a priority queue are shown in the following table, assuming that just priorities (no associated information) are to be stored in a priority queue. 

OPERATION DESCRIPTION 

PriorityQ() (constructor) create an empty priority queue 

boolean empty() return true iff the priority queue is empty 

void insert ( p ) add priority p to the priority queue 

removeMax() 

remove and return the highest priority from the priority queue (error if the priority queue is empty) 

A priority queue can be implemented using many of the data structures that we've studied (an array, a linked list, or a 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. 

Implementing priority queues using heaps 

Now let's consider how to implement priority queues using a heap. The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap: • 

The root of the heap is always in array[1]. • Its left child is in array[2]. • Its right child is in array[3]. • In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1]. • If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1). 

Here's an example, showing both the conceptual heap (the binary tree), and its array representation:  

Implementing insert 

When a new value is inserted into a priority queue, we need to: • 

Add the value so that the heap still has the order and shape properties, and • Do it efficiently! 

The way to achieve these goals is as follows: 

1. Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1). 

2. Step 1 above ensures that the heap still has the shape property; however, it may not have the order property. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-andswap procedure up the tree until we find that the order property holds, or we get to the root. 

Here's a series of pictures to illustrate inserting the value 34 into a heap: 

 

Because heaps have the order property, the largest value is always at the root. Therefore, the removeMax operation will always remove and return the root value; the question then is how to replace the root node so that the heap still has the order and shape properties. 

The answer is to use the following algorithm: 

1. Replace the value in the root with the value at the end of the array (which corresponds to the heap's rightmost leaf at depth d). Remove that leaf from the tree. 

2. Now work your way down the tree, swapping values to restore the order property: each time, if the value in the current node is less than one of its children, then swap its value with the larger child (that ensures that the new root value is larger than both of its children). 

Here's a series of pictures to illustrate the removeMax operation applied to the heap shown above.