Heaps: Notion of Heap and Heapsort

Page 253

A heap is a specialized binary tree structure where keys are assigned to its nodes, one key per node, and it must satisfy two primary conditions:

• The Shape Property: The binary tree must be essentially complete (or simply complete). This means that all levels of the tree are full, with the possible exception of the very last level, where only some rightmost leaves might be missing.

• There is exactly one such tree for any given number of nodes n, and its height is equal to $\lfloor \log_2 n \rfloor$.

• The Parental Dominance (or Heap) Property: The key in each node must be greater than or equal to the keys in its children. This property is automatically considered satisfied for all leaf nodes.

Consequently, key values in a heap are ordered top-down, meaning a sequence of values along any path from the root to a leaf is non-increasing.

However, there is no inherent left-to-right order among key values at the same level or between subtrees.

They are commonly implemented using arrays, where the children of a key at position i (1-indexed) are at positions 2i and 2i + 1, and the parent of a key at position i is at ⌊i/2⌋.

Heaps are particularly suitable for implementing priority queues.

Types of Heaps

The standard definition describes a max-heap, where the largest element is always at the root. A variation also exists:

• Min-Heap: Some sources define a heap where the key at each node is less than or equal to the keys in its children. In this variation, the root of the heap always contains its smallest element.

Bottom-Up Algorithm to Construct a Heap

The bottom-up heap construction algorithm efficiently builds a heap from a given array of elements. It works by first arranging the elements into an essentially complete binary tree structure and then "heapifying" it.

The process begins by considering the nodes from the last parental node down to the root.

For each parental node, the algorithm checks if the parental dominance property holds. If it doesn't, the node's key is exchanged with the larger of its children's keys.

This process of sifting down the key continues recursively within the subtree until the parental dominance is satisfied for that key.

This "heapification" is performed for each parental node, moving upwards through the tree until the root is processed.

ALGORITHM HeapBottomUp(H[1..n])
//Constructs a heap from elements of a given array
// by the bottom-up algorithm
//Input: An array H[1..n] of orderable items (1-indexed)
//Output: A heap H[1..n]

for i <- ⌊n/2⌋ downto 1 do   // last parental node up to the root
    p <- i                   // current parent node
    v <- H[i]                // value of the current parent
    heap <- false 

    while not heap and 2 ∗ p ≤ n do     // has children
      j ← 2 ∗ p                 // index of the left child

      if j < n              // Check if there are two children
        if H[j] < H[j + 1] 
          j <- j + 1 

      if v ≥ H[j]
        heap <- true 
      else
        H[p] <- H[j]      // Move the larger child up
        p <- j           // Move down to the child's position
    H[p] <- v           // Place v in its final position

Time Efficiency Analysis:

The bottom-up heap construction algorithm has a worst-case time efficiency of O(n).

More precisely, it performs fewer than 2n comparisons. This efficiency is achieved because most of the sifting-down operations occur on the lower levels of the tree, which contain more nodes but require fewer comparisons per node (since they are closer to the leaves and have shorter paths to traverse).

The cost of heapifying decreases as the algorithm moves up the tree, making the overall process highly efficient.

Heapsort Algorithm

Heapsort is an important sorting algorithm that organizes elements using a specialized binary tree structure called a heap. It is a two-stage algorithm.

Stage 1: Heap Construction

The first stage involves constructing a heap from the given input array. The most efficient method for this is the bottom-up heap construction algorithm, which takes an arbitrary array of elements and rearranges them to satisfy the heap properties.

Stage 2: Maximum Deletions

After the heap is constructed, the second stage of heapsort repeatedly extracts the largest element (which is always at the root of a max-heap) and places it into its final sorted position. This is done n - 1 times:

1. Swap: The root's key (the largest element) is exchanged with the last key in the heap.

2. Decrease Heap Size: The size of the heap is conceptually reduced by one, effectively excluding the newly placed largest element from the heap structure.

3. Heapify (Sift Down): The element that was moved to the root in step 1 is then "sifted down" to its appropriate position to restore the heap property for the reduced heap. This sifting-down process is identical to the one used in the bottom-up heap construction.

Time Efficiency Analysis:

The first stage (heap construction) has a time efficiency of O(n).

The second stage (maximum deletions) involves n-1 deletions. Each deletion operation, including swapping and sifting down, takes time proportional to the height of the heap, which is O(log n).

Therefore, the total time for the second stage is (n-1) * O(log n) = O(n log n).

Combining both stages, the overall worst-case time efficiency of Heapsort is O(n) + O(n log n) = O(n log n).

Heapsort's time efficiency is in $\Theta(n \log n)$ in both the worst and average cases.

Unlike Mergesort, Heapsort is an in-place sorting algorithm, meaning it does not require significant extra storage.