[Home]
[Chapter]
[Contents]
[Previous Algorithm]
[Next Algorithm]


Binary priority queues deletion


procedure delete ( var pq : tree ); var temp : tree; begin if pq = nil then Error {*** deletion on an empty queue ***} else if pq^.right = nil then pq := pq^.left else begin {*** promote left descendant up ***} pq^.k := pq^.left^.k; delete( pq^.left ); {*** rearrange according to constraints ***} if pq^.left = nil then begin pq^.left := pq^.right; pq^.right := nil end; if pq^.right <> nil then if pq^.left^.k < pq^.right^.k then begin {*** descendants in wrong order ***} temp := pq^.right; pq^.right := pq^.left; pq^.left := temp end end end;

C source (516b.del.c) Pascal source (516b.del.p)



© Addison-Wesley Publishing Co. Inc.