Heaps and Heapsort

Heaps and Heapsort

1. Heaps

   • priority queue: a multiset of items with an orderable characteristic called an item’s priority, with the following operations:
     • finding an item with the highest (i.e., largest) priority
     • deleting an item with the highest priority
     • adding a new item to the multiset
   • can be defined as a binary tree with keys assigned to its nodes, one key per node, provided the following two conditions are met:
     • The shape property—the binary tree is essentially complete (or simply complete), i.e., all its levels are full except possibly the last level, where only some rightmost leaves may be missing.
     • The parental dominance or heap property—the key in each node is greater than or equal to the keys in its children. (This condition is considered automatically satisfied for all leaves.)
     • For example, consider the trees of Figure 6.9. The first tree is a heap. The second one is not a heap, because the tree’s shape property is violated. And the third one is not a heap, because the parental dominance fails for the node with key 5
       • Note that key values in a heap are ordered top down; i.e., a sequence of values on any path from the root to a leaf is decreasing (nonincreasing, if equal keys are allowed). However, there is no left-to-right order in key values; i.e., there is no relationship among key values for nodes either on the same level of the tree or, more generally, in the left and right subtrees of the same node.
   • important properties of heaps
     • There exists exactly one essentially complete binary tree with n nodes. Its height is equal to [log_2 n]
     • The root of a heap always contains its largest element
     • A node of a heap considered with all its descendants is also a heap
     • A heap can be implemented as an array by recording its elements in the topdown, left-to-right fashion. It is convenient to store the heap’s elements in positions 1 through n of such an array, leaving H[0] either unused or putting there a sentinel whose value is greater than every element in the heap. In such a representation
       • the parental node keys will be in the first [n/2] positions of the array, while the leaf keys will occupy the last [n/2] positions
       • the children of a key in the array’s parental position i (1 ≤ i ≤ [n/2]) will be in positions 2i and 2i + 1, and, correspondingly, the parent of a key in position i (2 ≤ i ≤ n) will be in position [i/2].

2. Heapsort

   • Thus, heapsort’s time efficiency falls in the same class as that of mergesort. Unlike the latter, heapsort is in-place, i.e., it does not require any extra storage.
   • Timing experiments on random files show that heapsort runs more slowly than quicksort but can be competitive with mergesort.
   • This is a two-stage algorithm that works as follows.
     • Stage 1 (heap construction): Construct a heap for a given array.
     • Stage 2 (maximum deletions): Apply the root-deletion operation n − 1 times to the remaining heap.
   • As a result, the array elements are eliminated in decreasing order. But since under the array implementation of heaps an element being deleted is placed last, the resulting array will be exactly the original array sorted in increasing order. Heapsort is traced on a specific input in Figure 6.14.

Bilder und Dateien der Mindmap