Page 217 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Implementing d-Heaps as Arrays

1. The nodes of a d-heap can be stored in an array in breadth-fi rst order.
(a) allows indices for parents and children to calculated directly, eliminating the need
for pointers

4 4

1 2 3 4 5 6 7 8 9 10 11
8 4 2 7 9 10 h: 4 8 2 9 10 1 11 7 5 6 3

10 1 11 7 5 6 3 key: 6 7 13 4 11 12 15 4 10 5 8
5 6 8 15 11 12 13
2. If i is the index of an item x, then [(i−1)/d] is the index of p(x) and the indices of the children
of x are in the range [d(i−1) + 2 .. di + 1].
3. When the key of an item is decreased, we can restore heap-order, by repeatedly swapping
the item with its parent.

4. Similarly, for increasing an item’s key.
d-Heap Operations

item function fi ndmin(heap h);
return if h = {} [] null; ! h ≠ {} ®h(1) fi;
end;
procedure siftup(item i, integer x, modifies heap h);
integer p;
p := ⎝(x−1)/d⎤;
do p ≠ 0 and key(h(p)) > key(i) =>
h(x) := h(p); x := p; p := (p−1)/d⎤ ;
od;
h(x) := i;
end;
procedure insert(item i; modifies heap h);
siftup(i,|h| + 1,h);
end;
integer function minchild(integer x, heap h);
integer i, minc;
minc := d(x–1) + 2;
if minc > |h| =>return 0; fi;
i := minc + 1;
do i ≤ min {|h|,dx + 1} =>
if key(h(i)) < key(h(minc)) => minc := i; fi;
i := i + 1;

212 LOVELY PROFESSIONAL UNIVERSITY