analysis of algorithms When parent\'s key becomes smaller than one (or both) of
ID: 3678274 • Letter: A
Question
analysis of algorithms When parent's key becomes smaller than one (or both) of its children in a Heap, the sink method is called. The iterative algorithm for the sink method is given below: Sink (list, k, key, bound) while(2* lesserthanorequalto bound) do largerChild = 2*, k if (largerChild list[largerChild])) then largerChild = lagerChild + 1; enf if if(key > list[largerChild]) then break; exch(k, largerChild); //exchange values in loaction k and largerChild k = largerChild; end while Convert the above algorithm to a recursive algorithm Write a recurrence relation that computes the worst case running time tor your recursive algorithm. Use the maser method to approximate the order of the worst case running time o your recursive algorithm.Explanation / Answer
Priority Queue:
It is a queue.
There is a priority rule which points at any time to an item with highest priority. Adding a new item to the queue might change the most urgent item Often the largest key is the one with the highest priority; the meaning of the key is then related to the kind of application at hand.
A binary tree is heap-ordered if the key in each node is larger than or equal to the keys in that node's children.
Heapy(sink)
Parent O, in this case the root node, violates the heap condition.
Node O has been exchanged with its largest child node X, andfter that has been exchanged with its largest child node P. After those two operations the heap condition is satifed
The program HeapSort1 works like a selection sort.
More eciently we shall go back through the heap by making
little subheaps from the bottum up.
Every node is viewed as the root of a subheap and the sink
works well for such heaps too.
A node with two subheaps as its children becomes a heap
calling sink on that node.
Working backward calling sink on each node we inductively
establish the heap condition.
Priority Queues
Heaps
Heapsort
Sorting by using a Heap
Heapsort
Example
Sink method in more detail
private void sink(int k, int N) {
while (2*k <= N) { // 1
int j=2*k; // 2
if (j<N && less(j, j+1)) j++; // 3
if (!less(k, j)) break; // 4
exch(k, j); k = j; // 5
}
}
Node at k has left child at 2 k, stop if 2 k>N.
2 Start at left node withj. If j==N
then j is even: no right node. Careful treatment of last node!
private void sink(int k, int N) {
while (2*k <= N) { // 1
int j=2*k; // 2
if (j<N && less(j, j+1)) j++; // 3
if (!less(k, j)) break; // 4
exch(k, j); k = j; // 5
}
}
If j<N then a right child node exists; if j == N
there is no right child node. Largest child found at j.
4 If node at k not smaller than node at j: nothing todo, break.
5 If node at j larger than node at k: exchange them
for (int k = N/2; k >= 1; k--) {
sink(a, k, N);
}
Node with indexk=N=2 is last node with child nodes (i.e.the last parent node). From there go up the tree, level ordered, and heapify with sink
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
In-place sorting: exchange max item (index 1) with last node of unsorted part of the tree (index N).
Functions as a selection sort. First decrement N and then heapify by calling sink on new root node.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.