מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות - פסוודו-קוד

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