לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי



להלן הפסוודו-קוד המלא לערימה בינרית:


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