מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות - פסוודו-קוד
להלן הפסוודו-קוד המלא לערימה בינרית:
Binary-Heap
# An array of the values stored.
1 Values
# The size (number of entries used in Values).
2 size
# Creates a priority queue.
Make-Heap()
1 bh = Binary-Heap()
2 bh.size = 0
# max-size is some global constant.
3 bh.Values = Array(max-size)
# Returns the index of the left child.
Left-Child(i)
1 return 2 * i
# Returns the index of the right child.
Right-Child(i)
1 return 2 * i + 1
# Returns the index of the parent.
Parent(i)
1 return ⌊i / 2⌋
# Returns the size of a heap (bh).
Size(bh)
1 return bh.size
# Returns the maximum size of a heap (bh).
Max-Size(bh)
1 return Length(bh.Values)
# Returns the smallest value in a heap (bh).
Min(bh)
1 return bh.Values[1]
# Utility function for maintaining the heap invariant.
# Recursively corrects a violation at some index (i).
Bubble-Up(bh, i)
1 if i == 1
2 return
3 p = Parent(i)
4 if bh.Values[p] <= bh.Values[i]
5 return
# This swaps the two values.
6 bh.Values[p] <-> bh.Values[i]
7 Bubble-Up(bh, p)
# Inserts a value (v) to a binary heap (bh).
Insert(bh, v)
1 bh.Values[++bh.size] = v
2 Bubble-Up(bh, bh.size)
# Utility function for maintaining the heap invariant.
# Recursively corrects a violation at some index (i).
Bubble-Down(bh, i)
1 l = Left-Child(i)
2 r = Right-Child(i)
3 if l <= bh.size and bh.Values[l]
# Makes a binary heap from an array (Values).
Build-Heap(Values)
1 bh = Make-Priority-Queue()
2 bh.size = Length(Values)
3 for i in [1, ..., Length(Values)]
4 bh.Values[i] = Values[i]
5 for i in [Length(Values), ..., 1]
6 Bubble-Down(bh, i)
7 return bh