Heap

Heap (Chapter 6)

Binary heap structure

An array represents a nearly complete binary tree. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

note: the following indices are 1-based.

Basic index accessors

• PARENT(i) = floor(i/2)

• LEFT(i) = 2*i

• RIGHT(i) = 2*i+1

Characteristics

• 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. As a result, an n-element heap has height floor(lgn).

• In the array storing an n-element heap, the leaves are the nodes indexed by floor(n/2)+1, floor(n/2)+2, ..., n.

Max-heap/min-heap

In a max-heap, the value of a node is at most the value of its parent A[PARENT(i)]>=A[i]. Thus the largest element is a max heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself. Min-heap is organized in the opposite way.

Basic procedures

1. MAX-HEAPIFY

   Given an array A and an index i, it is assumed that the binary tree rooted at LEFT(i) and RIGHT(i) are max-heaps, but A[i] may be smaller than its children, thus violating the max-heap property. The function of MAX-HEAPIFY is to rebuild the subtree rooted at index i to a max-heap.

   Basic steps: compare A[i] with its children, if it is smaller than any of them, swap it with the largest child. Call the MAX-HEAPIFY recursively on the swapped child.

   Time complexity: O(lgn)

2. BUILD-MAX-HEAP

   Producing a max heap from an unordered input array.

   Basic steps: an iteration of calling MAX-HEAPIFY on the input array indexed from floor(n/2) to 1.

   Initialization: given the fact that all the nodes indexed by floor(n/2)+1, floor(n/2)+2, ..., n are leaves of the tree, each of them is a 1-element trivial max-heap

   Loop invariant: since all the children of A[i] are numbered higher than itself, if both of the children nodes are max-heap, the process of making the subtree starting from A[i] is a process of MAX-HEAPIFY

   Time complexity: O(n)

Application 1: heapsort

1. build the input array (length = n) into a max heap using BUILD-MAX-HEAP

2. for i = n to 1:

   exchange A[1] and A[i]
   
   perform MAX-HEAPIFY on the subarray (1 to i-1)
   

Time complexity: O(nlgn)

Application 2: priority queue

In a max-priority queue, the following basic operations are supported:

1. MAXIUM(A): return the element with highest priority

   return the first root node in the max-heap

2. EXTRACT-MAX(A): removes and returns the element with highest priority

   set the max to the first root node in the max-heap

   put the last element in A to the first,

   set the length of A to n-1

   call the MAX-HEAPIFY on the subarray (1 to n-1)

   return max

3. INCREASE-KEY(A, i, k): increase the priority of an element at index i

   if k < A[i]: return error

   else: traverse a path from A[i] to the root, if the value is larger than the parent, swap them and continue...

4. INSERT(A, e): insert a new element into the queue

   add a new element to the end of the heap with a lowest priority

   call the INCREASE-KEY(A, i, k) on this new element to set the priority to the right value

Young tableaus (Problem 6-3)

Definition: an m x n Young tableau is an m x n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are sorted from top to bottom. Some of the entries may be empty, which are treated as infinite large or small depending on the sorting order.

1. EXTRACT-MIN: O(m+n)

   remove and return A[1,1]

   compare A[2, 1] and A[1, 2]: if A[2, 1] is smaller, set A[1,1] = A[2, 1], call EXTRACT-MIN recursively on the sub-matrix (row: 1-m, column 2-n). If A[1,2] is smaller, set A[1,1] = A[1,2], call EXTRACT-MIN recursively on the sub-matrix (row: 2-m, column 1-n)

2. INSERT: O(m+n)

   add the new element to the end of the matrix (m, n)

   compare it with the elements stored in (m-1, n) and (m, n-1). If A[m, n] is smaller than the smaller of A[m-1, n] and A[m, n-1], swap them, repeat the process after the swapping.

3. SORT: O(n^3 (sorting n x n elements using a Young tableau)

   Build the Young tableau by inserting each element into an empty one: O(n^3)

   extract each smallest element from it using EXTRACT-MIN

4. Search whether a given number is stored in a given m x n Young tableau: O(m+n)

   Compare the given number with A[1,n], if it is smaller than A[1,n], search it in the sub-matrix (rows: 1m, columns: 1(n-1) ); if it is larger than A[1,n], search it in the sub-matrix (rows: 1~(m-1), columns: 1~n)