מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/מימושים חלופיים לArray-To-Heap/שאלה

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

# 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	Arrange(bh)
	
6	return bh

קטע קוד זה מקבל מערך, ומחזיר ערימה בינרית . איפ חוכך בדעתו כיצד מומשה הפונקציה Arrange. (אנו למעשה כבר ראינו את המימוש הבא:

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Down(bh, i)

אך הוא אינו יודע זאת).

מספר אפשרויות עולות על דעתו:

Arrange(bh)
1	for i in [⌊Length(bh.Values) / 2⌋, ..., 1]
2		Bubble-Down(bh, i)

Arrange(bh)
1	Merge-Sort(bh.Values)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Down(bh, i)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Up(bh, i)

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Up(bh, i)

עבור כל אחת מהאפשרויות, אנא הוכח או הפרך את הטענה שבהכרח תתקבל ערימה תקנית, ונתח את הסיבוכיות במקרה הגרוע (בלי קשר לשאלה האם תתקבל ערימה תקנית).