Heap data structure, implementing the Priority Queue ADT Heap = { elements array A; // assumed to be large enough int next_element; // position of next element, initially 0 } Parent(n) = (n / 2) - 1 Left(n) = 2*n + 1 Right(n) = 2*n + 2 EmptyHeap(size): // create an empty heap that can hold up to size elements return { A = NewArray(size); next_element = 0 } GetNext(H): out := H.A[0] // root of the "tree" H.A[0] := H.A[H.next_element - 1] H.next_element := H.next_element - 1 // one less element BubbleDown(H,0) return out BubbleDown(H,n): if (Left(n) < H.next_element and H.A[n] < H.A[Left(n)]) or (Right(n) < H.next_element and H.A[n] < H.A[Right(n)]) then // heap property does not hold; let's fix it if (Right(n) >= H.next_element) then // only left exists Swap(H,n,Left(n)) BubbleDown(H,Left(n)) else // we swap with the highest children highest_pos := if H.A[Left(n)] >= H.A[Right(n)] then Left(n) else Right(n) Swap(H,n,highest_pos) BubbleDown(H,highest_pos) InsertWithPriority(H,p): H.A[H.next_element] := p H.next_element := H.next_element + 1 BubbleUp(H,H.next_element) BubbleUp(H,n): if n > 0 and H.A[n] > H.A[Parent(n)] then Swap(H,n,Parent(n)) BubbleUp(H,Parent(n)) Swap(H,n,m): tmp := H.A[n] H.A[m] := H.A[n] H.A[n] := tmp