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

דף זה עוסק בתורי קדימויות, בפרט במימוש ערימה בינרית (binary heap). תור קדימויות משמש לשמירת קבוצת איברים כאשר:

• הקבוצה דינמית (נתן להוסיף ולמחוק איברים).
• יש לענות בצורה יעילה על השאלה מהו האיבר הקטן ביותר (או לחלופין הגדול ביותר).

לעומת זאת, תור קדימויות אינו משמש לשמירת קבוצת איברים כאשר יש לחפש בצורה יעילה איבר מסוים (כמו האם האיבר 124 מופיע בקבוצה).

תבנית:מבנה תבנית

ממשק

הנה הממשק של תור קדימויות:

# Creates a priority queue.
Make-Heap()

# Inserts a value (v) to a priority queue (pq).
Insert(pq, v)

# Returns the smallest value in a priority queue (pq).
Min(pq)

# Removes the smallest value from a priority queue (pq).	
Delete-Min(pq)

# Returns the size of a priority queue (pq).
Size(pq)

ולהלן דוגמה לשימוש בו:

1	Insert(pq, 94)
2	Insert(pq, 91)
3	Insert(pq, 99)
4	Insert(pq, 93)

	# Prints 91.
5	Print( Min(pq) )

	# Removes 91.
6	Delete-Min(pq)
	# Removes 93.
7	Delete-Min(pq)

	# Prints 94.
8	Print( Min(pq) )

בדף זה נעסוק במימוש ספציפי לממשק זה - מימוש הערימה הבינרית (תבנית:קוד בשורה). שאר הדף עוסק במימוש זה.

ארגון המידע

שומרים מערך של האיברים, ומשתנה המציין כמה איברים נמצאים כרגע בשימוש:

Binary-Heap
	# An array of the values stored.
1	Values
	# The size (number of entries used in Values).
2	size

ייצוג העץ

ילדים והורים

כאמור, המבנה הוא למעשה מערך, אלא שאפשר לחשוב עליו כעץ בינרי (עץ שבו לכל צומת יש לכל היותר שני ילדים):

1. השורש הוא באינדקס 1.
2. אם צומת הוא באינדקס $i$, אז:
   1. ילדו השמאלי (אם יש לו) הוא באינדקס $2\cdot i$.
   2. ילדו הימני (אם יש לו) הוא באינדקס $2\cdot i+1$.
   3. אביו (אם יש לו) הוא באינדקס $\lfloor i/2\rfloor$.

# 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⌋

אחת התכונות המועילות של העץ המתקבל, הוא שגובהו לוגריתמי במספר האיברים:

תכונת הערימה

תבנית:הארה

תבנית:הארה

פעולות פשוטות

קל מאד לראות מתכונות הערימה את המשפט הבא.

בעזרת המשפט, נממש כעת את הפעולות הפשוטות תבנית:קוד בשורה, תבנית:קוד בשורה, ותבנית:קוד בשורה. כ"א מהן היא $O(1)$ באופן טריוויאלי.

# 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]

פעולת Insert

כדי להכניס איבר חדש לערימה, ראשית מכניסים צומת חדש כצומת האחרון, ולאחר מכן מבעבעים אותו מעלה למקומו המתאים.

תבנית:מבנה תבנית

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

# 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)

תבנית:משפט

תבנית:הוכחה

תבנית:משפט

תבנית:משפט

פעולת Delete-Min

כדי להוציא את האיבר הקטן ביותר מהערימה, ראשית נחליף את צמתו בצומת האחרון, ולאחר מכן מבעבעים את הצומת מטה למקום המתאים.

תבנית:מבנה תבנית

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

# 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] and bh.size and bh.Values[l] < bh.Values[i]
4		smallest = l 
5	else
6		smallest = i
		
7	if r <= bh.size and bh.Values[r] < bh.Values[smallest]
8		smallest = r
		
9	if smallest == i
10		return
		
	# This swaps the two values.
11	bh.Values[i] <-> bh.Values[smallest]
	
12	Bubble-Down(bh, smallest)
		
		
# Removes the smallest value from a heap (bh).	
Delete-Min(bh)
14	v = Min(bh)
	
15	bh.Values[1] = bh.Values[bh.size--]
	
16	Bubble-Down(bh, 1)
	
17	return v

תבנית:משפט

תבנית:משפט

אלגוריתם המיון Heapsort

אפשר להשתמש בערימה בינרית כדי למיין מערך. להלן (גרסה אחת אפשרית) של אלגוריתם המיון Heapsort:

#/ Heap sort. 
# Takes an array (Values), and sorts it in increasing order.
Heapsort(Values)
1	n = Length(Values)
	
2	bh = Make-Binary-Heap()
	
3	for i in [1, ..., Length(Values)]		
4		Insert(bh, Values[i])
	
5	for i in [1, ..., Length(Values)]		
6		Values[i] = Delete-Min(bh)

בשיעורי הבית תתבקש להוכיח את נכונות האלגוריתם ולהראות שסיבוכיותו $\mathrm{\Theta }(n\cdot \log (n))$.

בניה ממערך

לבסוף נעסוק בבעיה אחרונה - בניית ערימה בינרית ממערך (שגודלו $n$):

# Makes a binary heap from an array (Values).
Build-Heap(Values)

המימוש הנאיבי

לכאורה קל מאד לממש את {{קוד בשורה|Build-Heap ע"י לולאה של פעולות תבנית:קוד בשורה:

# Makes a binary heap from an array (Values).
Build-Heap(Values)
1	bh = Make-Priority-Queue()
	
2	for i in [1, ..., Length(Values)]
3		Insert(bh, Values[i])
			
4	return bh

תבנית:משפט

מימוש בעזרת תבנית:קוד בשורה

להלן מימוש יעיל יותר, המתבסס כולו על תבנית:קוד בשורה:

# 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

תבנית:משפט

תבנית:הוכחה

תבנית:משפט

תבנית:הוכחה