Page 218 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

od; Notes
return minc;
end;
procedure siftdown(item i, integer x, modifies heap h);
integer c;
c := minchild(x,h);
do c ≠≠0 and key(h(c)) < key(i) =>
h(x) := h(c); x := c; c := minchild(x,h);
od;
h(x) := i;
end;
procedure delete(item i, modified heap h);
item j; j := h(|h|); h(|h|) := null;
–1
if i ≠ j and key(j) ≤ key(i) =>siftup(j,h (i),h);
| i ≠ j and key(j) > key(i) =>siftdown(j,h-1(i),h);
fi;
end;
item function deletemin(modifies heap h);
item i;
if h = {} => return null; fi;
i := h(1); delete(h(1),h);
return i;
end;
procedure changekey(item i, keytype k, modified heap h);
item ki; ki := key(i); key(i) := k;
if k < ki=>siftup(i,h-1(i),h);
| k > ki =>siftdown(j,h-1(i),h);
fi;
end;

D-Heap Algorithms

A d-heap is a tree with the property that a parent’s value is smaller than (or equal to) the value of
any of its d children. For example, the min heap we have seen in class is a 2-heap.

Given N the number of elements in the d-heap, in terms of d and N what is the time cost in the
worst case (big Oh notation) of each of the following operations.
1. buildHeap: Builds a d-heap from a list of nautrals read from standard input.
2. insertHeap: Inserts a new element into the d-heap.

3. decreasKey (p, Δ): lowers the value of the item at position p by a positive amount Δ.
4. increaseKey (p, Δ): increases the value of the item at position p by a positive amount Δ.
5. remove: removes the node at position p from the d-heap. This is done by performing
decreaseKey (p, ∞) and then performing deleteMin ().

LOVELY PROFESSIONAL UNIVERSITY 213