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

להלן אלגוריתם הידוע בשם Heapsort (מיון תור קדימות):

# Heap sort. 
# Takes an array (Values), and sorts it in increasing order.
Heapsort(Values)
1	bh = Array-To-Heap(Values)

2	for i in [1, ..., Length(Values)]
3		Values[i] = Delete-Min(bh)

1. אנא הוכח שהאלגוריתם עובד
2. אנא נתח את סיבוכיות האלגוריתם.

להלן ווריאציה אחרת של האלגוריתם:

# Heap sort. 
# Takes an array (Values), and sorts it in increasing order.
Heapsort(Values)
1	bh = Make-Binary-Heap()

2	for i in [1, ..., Length(Values)]		
3		Insert(bh, Values[i])

4	for i in [1, ..., Length(Values)]		
5		Values[i] = Delete-Min(bh)

אנא חזור על שני הסעיפים הקודמים לגבי ווריאציה זו.