Create max heap for array
I have a homework question that says:
Problem 1: Given the array [22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66] Build the maximum heap for an array. Show all steps without missing any details.
This is my understanding of the maximum heap from internet research:
Max. the heap is an array, which can be more easily represented by a binary tree, where the parent node is always larger than it is, and "every time you add a child, you add it to the left so that every time the tree increases its height, it is a full tree "
Anyway this is what I created
I thought it was the correct answer until I read question 2 of my homework, which says:
Problem 2: Using the same array as in Problem 1, sort the array using Heapsort. Show all steps without missing any details.
Now I am confused. I may have answered problem number 2 ...
source to share
You are building a tree, but you are not updating your array. The array reflects the structure of the heap. The first element, which is the largest element in the array, and the next two elements are the left and right children of that.
The idea is that you built a heap so that you replace the last and first elements of the array, and then work on the same array, but only using elements 0 ... array.size - 2. The heap condition is invalid and you call heapify to get the correct heap structure on a smaller array. This gives you again the largest element in that smaller array at the first position. You swap the first and last elements in the smaller array and create a bunch of array that has 2 fewer elements. But you have two elements at the end that are sorted (the largest element from the entire array and the next largest element (which is the largest element from the first smaller array)). You will do this until you have a rest array that has no elements.
Have a look at Heap Sort Chart on the German Wikipedia . First, you will see an unsorted array. The smaller black box indicates the position in the array. The first tree is a heap.
Unsorted array
23 | 1 | 6 | 19 | 14 | 18 | 8 | 24 | 15
Heapified Array
24 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 15
First iteration
Swap First (Biggest Element in Array) with last Element (could be anything)
15 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 24
heap condition is invalid
Build heap on array.size - 2
23 | 19 | 18 | 15 | 14 | 8 | 6 | 1 || 24
Swap first and last element in smaller heap
1 | 19 | 18 | 15 | 14 | 8 | 6 | 23 || 24
Build heap on array.size - 3
19 | 15 | 18 | 1 | 14 | 8 | 6 || 23 | 24
Swap first and last element on that smaller heap and build heap on array.size - 4
until you cant shrink the heap anymore, you'll receive
|| 1 | 8 | 14 | 15 | 18 | 19 | 23 | 24
The invariant is that your tree is a heap before and after each iteration. This is why it works. Since you will always change the largest element at the end of the heapified array.
source to share