Please enable JavaScript.
Coggle requires JavaScript to display documents.
M9 (How can we construct a heap for a given list of keys? There are two…
M9
How can we construct a heap for a given list of keys? There are two principal
alternatives for doing this.
-
The alternative (and less efficient) algorithm constructs a heap by successive
insertions of a new key into a previously constructed heap; some people call it
the top-down heap construction algorithm. So how can we insert a new key K
into a heap? First, attach a new node with key K in it after the last leaf of the
existing heap. Then sift K up to its appropriate place in the new heap as follows.
Compare K with its parent’s key: if the latter is greater than or equal to K, stop
(the structure is a heap); otherwise, swap these two keys and compare K with its
new parent. This swapping continues until K is not greater than its last parent or
it reaches the root
Obviously, this insertion operation cannot require more key comparisons than
the heap’s height. Since the height of a heap with n nodes is about log2 n, the time
efficiency of insertion is in
delete a node
Deleting the root’s key from a heap. The key to be deleted is swapped
with the last key after which the smaller tree is “heapified” by exchanging
the new key in its root with the larger key in its children until the parental
dominance requirement is satisfied.
Maximum Key Deletion from a heap
Step 1 Exchange the root’s key with the last key K of the heap.
Step 2 Decrease the heap’s size by 1.
Step 3 “Heapify” the smaller tree by sifting K down the tree exactly in the
same way we did it in the bottom-up heap construction algorithm.That
is, verify the parental dominance for K: if it holds, we are done; if not,
swap K with the larger of its children and repeat this operation until
the parental dominance condition holds for K in its new position.
A heap 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.)
-
a. the parental node keys will be in the first floor(n/2) positions of the array,
while the leaf keys will occupy the last floor(n/2) positions;
b. the children of a key in the array’s parental position i (1≤ i ≤ floor(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 floor(i/2)
Thus, we could also define a heap as an array H[1..n] in which every element
in position i in the first half of the array is greater than or equal to the elements
in positions 2i and 2i + 1
Heapsort
sorting algorithm
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.
Since we already know that the heap construction stage of the algorithm is in
O(n), we have to investigate just the time efficiency of the second stage
For both stages,
we get O(n) + O(n log n) = O(n log n)