6. Heapsort

1.  Like merge sort, but unlike insertion sort, heapsort’s running time is O(n lg n). Like insertion sort, but unlike merge sort, heapsort sorts in place.

 

2.  The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Although A[1...A.length] may contain numbers, only the elements in A[1...A.heap-size], where 0 ≤ A.heap-size ≤ A.length, are valid elements of the heap. The root of the tree is A[1], and given the index i of a node, the index of its parent is ⌊i/2⌋ and the index of its left and right child is 2i and 2i+1 respectively.

 

3.  There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds,

the values in the nodes satisfy a heap property, the specifics of which depend on

the kind of heap. In a max-heap, the max-heap property is that for every node i

other than the root, A[PARENT(i)] ≥ A[i]. Thus, the largest element in amax-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself. A min-heap is organized in the opposite way.

 

4.  Viewing a heap as a tree, we define the height of a node in a heap to be the

number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root. Since a heap of n elements is based on a complete binary tree, its height is θ(lg n). The basic operations on heaps run in time at most proportional to the height of the tree and thus take O(lg n) time.

 

5.  The inputs of sink are an array A and an index i into the array. When it is called, sink assumes that the binary trees rooted at LEFT[i] and RIGHT[i] are maxheaps, but that A[i] might be smaller than its children, thus violating the max-heap property. sink lets the value at A[i] “float down” in the max-heap so that the subtree rooted at index i obeys the max-heap property:

 

void sink (int i) {
    while ( true ) {
        int largest = i ;
        int left = i << 1;
        if ( left <= this.size && gt(left , largest) ) largest = left;
        int right = left + 1;
        if ( right <= this.size && gt(right , largest) ) largest = right;
        if ( largest == i ) break;
        swap(i, largest);
        i = largest;
    }
}

boolean gt(int i , int j) {
    // array index starts from 0
    return this.arr[i-1] > this.arr[j-1];
}

void swap(int i , int j) {
    // array index starts from 0
    int temp = this.arr[--i];
    this.arr[i] = this.arr[--j];
    this.arr[j] = temp;
}

We can characterize the running time of sink on a node of height h as O(h) = O(lg n)

 

6.  We can use the sink in a bottom-up manner to convert an array A[1...n], where n = A.length, into a max-heap. The elements in the subarray A[⌊n/2⌋+1...n] are all leaves of the tree, and so each is a 1-element heap to begin with. The method heapfy goes through the remaining nodes of the tree and runs sink on each one:

 

void heapfy() {
    for ( int i = this.size >> 1 ; i > 0; i -- ) {
        sink(i);
    }
}

We can easily prove the correctness of the above algorithm by the following invariant: At the start of each iteration of the for loop, each node i+1, i+2, ... , n is the root of a max-heap. Since an n-element heap has height ⌊lgn⌋ and at most 

⌈n/2^(h+1)⌉ nodes of any height h. The time required by heapfy when called on a node of height h is O(h) and so we can express the total cost of heapfy as O(∑(h=0 to lgn) ( h * n/2^h) ) = O(n). So heapfy produces a min-heap from an unordered linear array in linear time.

 

7.  The heapsort algorithm starts by using heapfy to build a max-heap on the input array A[1...n], where n =A.length. Since the maximum element of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. The children of the root remain max-heaps with last element regarded from the heap, but the new root element might violate the max-heap property. All we need to do to restore the max-heap property is call sink(1), which leaves a max-heap in A[1...n-1]. The heapsort algorithm then repeats this process for the max-heap of size n-1 down to a heap of size 2:

 

void heapsort() {
    this.size = this.arr.length;
    heapfy();
    while (this.size > 1 ) {
        swap( 1 , this.size--);
        sink(1);
    }
}

 

The heapsort method takes time O(n lg n), since the call to heapfy takes time O(n) and each of the n-1 calls to sink takes time O(lg n).

 

8.  Heapsort is an excellent algorithm, but a good implementation of quicksort usually beats it in practice. One of the most popular applications of a heap is as an efficient priority queue. As with heaps, priority queues come in two forms: max-priority queues and min-priority queues.

 

9.  A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. A max-priority queue supports the following operations:

    1)  INSERT(S , x) inserts the element x into the set S, which is equivalent to the operation S=S U {x}.

    2)  MAXIMUM(S) returns the element of S with the largest key.

    3)  EXTRACT-MAX(S) removes and returns the element of S with the largest key.

    4)  INCREASE-KEY(S, x, k) increases the value of element x’s key to the new value k, which is assumed to be at least as large as x’s current key value.

 

10.  We can use max-priority queues to schedule jobs on a shared computer. The max-priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted,

the scheduler selects the highest-priority job from among those pending by calling EXTRACT-MAX. The scheduler can add a new job to the queue at any time by calling INSERT.

 

11.  A min-priority queue can be used in an event-driven simulator. The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be

simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future. The simulation program calls EXTRACT-MIN at each step to choose the next event to simulate. As new events are produced, the simulator inserts them into the min-priority queue by calling INSERT.

 

12.  When we use a heap to implement a priority queue, therefore, we often need to store a handle to the corresponding application object in each heap element. Similarly, we need to store a handle to the corresponding heap element in each application object. Here, the handle would typically be an array index. Because heap elements change locations within the array during heap operations, an actual implementation, upon relocating a heap element, would also have to update the array index in the corresponding application object. 

 

13.  The maximum method can be implemented as :

 

 

int maximum() {
  if (this.size < 1) throw new NoSuchElementException("priority queue is empty!");
  return get(1);
}

int get(i) {
    // array index starts from 0
    return this.arr[0];
}

The extractMax method can be implemented as :

 

int extractMax() {
    if (this.size < 1) throw new NoSuchElementException("priority queue is empty!");
    swap(1, this.size--);
    if ( this.size > 0 ) sink(1);
    return get(this.size + 1);
}

The running time of extractMax is O(lg n), since it performs only a constant amount of work on top of the O(lg n) time for sink.

 

14.  The method increaseKey first updates the key of element A[i] to its new value. Because increasing the key of A[i] might violate the max-heap property,the method then traverses a simple path from this node toward the root to find a proper place for the newly increased key. As increaseKey traverses this path, it repeatedly compares an element to its parent, exchanging their keys and continuing if the element’s key is larger, and terminating if the element’s key is smaller, since the max-heap property now holds:

 

void increaseKey( int i , int newValue) {
    if ( newValue <= get(i) ) throw new IllegalArgumentException("the newValue should be bigger than the existing value.");
    set(i, newValue);
    swim(i);
}

void set(int i, int value) {
    // array index starts from 0
    this.arr[i-1] = value;
}

void swim (int i) {
  int parent = i >> 1;
  while( parent > 0 && gt(i, parent) ) {
      swap(i, parent);
      i = parent;
      parent = i >> 1;
  } 

}

 

The running time of increaseKey on an n-element heap is O(lg n), since the path

traced from the node updated to the root has length O(lg n).

 

15.  The method insert first expands the max-heap by adding to the tree a new leaf whose key is the new value. Then it calls swim to put this new node to its correct position thus maintain the max-heap property:

 

void insert(int newValue) {
    set(++ this.arr.size , newValue);
    swim(this.arr.size);
}

The running time of insert on an n-element heap is O(lg n).

 

16.  In summary, a heap can support any priority-queue operation on a set of size n in O(lg n) time.