Hipsort — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
|||
Ред 123:
jasan način uključivanja A[i] u hip: A[i] se upoređuje sa većim od sinova, i
zamenjuje se sa njim ako je potrebno. Sa zamenama se nastavlja naniže niz stablo, dok prethodna vrednost elementa A[i] ne dođe do mesta na kome je veća od oba sina.
== Example ==
Let { 6, 5, 3, 1, 8, 7, 2, 4 } be the list that we want to sort from the smallest to the largest. (NOTE, for 'Building the Heap' step: Larger nodes don't stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.)
[[File:Heapsort-example.gif|350px|thumb|right|An example on heapsort.]]
'''1. Build the heap'''
{| class="wikitable"
|-
! Heap !! newly added element !! swap elements
|-
| nul || 6 ||
|-
| 6 || 5 ||
|-
| 6, 5 || 3 ||
|-
| 6, 5, 3 || 1 ||
|-
| 6, 5, 3, 1 || 8 ||
|-
| 6, '''5''', 3, 1, '''8 '''|| || 5, 8
|-
| '''6''', '''8''', 3, 1, 5 || || 6, 8
|-
| 8, 6, 3, 1, 5 || 7 ||
|-
| 8, 6, '''3''', 1, 5, '''7''' || || 3, 7
|-
| 8, 6, 7, 1, 5, 3 || 2 ||
|-
| 8, 6, 7, 1, 5, 3, 2 || 4 ||
|-
| 8, 6, 7, '''1''', 5, 3, 2, '''4''' || || 1, 4
|-
| 8, 6, 7, 4, 5, 3, 2, 1 || ||
|}
'''2. Sorting.'''
{| class="wikitable"
|-
! Heap !! swap elements !! delete element !! sorted array !! details
|-
| '''8''', 6, 7, 4, 5, 3, 2, '''1''' || 8, 1 || || || swap 8 and 1 in order to delete 8 from heap
|-
| 1, 6, 7, 4, 5, 3, 2, '''8''' || || 8 || || delete 8 from heap and add to sorted array
|-
| '''1''', 6, '''7''', 4, 5, 3, 2 || 1, 7 || || 8 || swap 1 and 7 as they are not in order in the heap
|-
| 7, 6, '''1''', 4, 5, '''3''', 2 || 1, 3 || || 8 || swap 1 and 3 as they are not in order in the heap
|-
| '''7''', 6, 3, 4, 5, 1, '''2''' || 7, 2 || || 8 || swap 7 and 2 in order to delete 7 from heap
|-
| 2, 6, 3, 4, 5, 1, '''7''' || || 7 || 8 || delete 7 from heap and add to sorted array
|-
| '''2''', '''6''', 3, 4, 5, 1 || 2, 6 || || 7, 8 || swap 2 and 6 as they are not in order in the heap
|-
| 6, '''2''', 3, 4, '''5''', 1 || 2, 5 || || 7, 8 || swap 2 and 5 as they are not in order in the heap
|-
| '''6''', 5, 3, 4, 2, '''1'''|| 6, 1 || || 7, 8 || swap 6 and 1 in order to delete 6 from heap
|-
| 1, 5, 3, 4, 2, '''6''' || || 6 || 7, 8 || delete 6 from heap and add to sorted array
|-
| '''1''', '''5''', 3, 4, 2 || 1, 5 || || 6, 7, 8 || swap 1 and 5 as they are not in order in the heap
|-
| 5, '''1''', 3, '''4''', 2 || 1, 4 || || 6, 7, 8 || swap 1 and 4 as they are not in order in the heap
|-
| '''5''', 4, 3, 1, '''2''' || 5, 2 || || 6, 7, 8 || swap 5 and 2 in order to delete 5 from heap
|-
| 2, 4, 3, 1, '''5''' || || 5 || 6, 7, 8 || delete 5 from heap and add to sorted array
|-
| '''2''', '''4''', 3, 1 || 2, 4 || || 5, 6, 7, 8 || swap 2 and 4 as they are not in order in the heap
|-
| '''4''', 2, 3, '''1''' || 4, 1 || || 5, 6, 7, 8 || swap 4 and 1 in order to delete 4 from heap
|-
| 1, 2, 3, '''4''' || || 4 || 5, 6, 7, 8 || delete 4 from heap and add to sorted array
|-
| '''1''', 2, '''3''' || 1, 3 || || 4, 5, 6, 7, 8 || swap 1 and 3 as they are not in order in the heap
|-
| '''3''', 2, '''1''' || 3, 1 || || 4, 5, 6, 7, 8 || swap 3 and 1 in order to delete 3 from heap
|-
| 1, 2, '''3''' || || 3 || 4, 5, 6, 7, 8 || delete 3 from heap and add to sorted array
|-
| '''1''', '''2''' || 1, 2 || || 3, 4, 5, 6, 7, 8 || swap 1 and 2 as they are not in order in the heap
|-
| '''2''', '''1''' || 2, 1 || || 3, 4, 5, 6, 7, 8 || swap 2 and 1 in order to delete 2 from heap
|-
| 1, '''2''' || || 2 || 3, 4, 5, 6, 7, 8 || delete 2 from heap and add to sorted array
|-
| '''1''' || || 1 || 2, 3, 4, 5, 6, 7, 8 || delete 1 from heap and add to sorted array
|-
| || || || 1, 2, 3, 4, 5, 6, 7, 8 || completed
|}
== Reference ==
| |||