Data Structures: Removing from a Heap and Heapsort

Think about this MaxHeap:

0	1	2	3	4	5	6
23	12	19	7	10	18	14

Remember, children are found with this formula:

Left child: 2i + 1

Right child: 2i + 2

Parents are found with this formula:

Parent: (i - 1) / 2

If we have a maxheap, the children are smaller than the parents.  If we have a minheap, the children are larger than the parents.  This is a maxheap, so all parents are larger than their children.

To add to a maxheap, we put the new value at the next available position in the array then swap up.  In the file for your assignment, we call this process reheapUp.

If we add the value 20 to the maxheap above, we get this:

0	1	2	3	4	5	6	7
23	12	19	7	10	18	14	20

We swap 20 (index 7) with its parent, if the parent is smaller.  The parent value is 7 (index 3) so we swap up.

0	1	2	3	4	5	6	7
23	12	19	20	10	18	14	7

We swap 20 (index 3) with its parent, if the parent is smaller.  The parent value is 12 (index 1) so we swap up.

0	1	2	3	4	5	6	7
23	20	19	12	10	18	14	7

We swap 20 (index 1) with its parent, if the parent is smaller.  Here it’s not so we’re done.

To remove from the maxheap, we could just remove the top element and swap elements upward.  However, this would leave a gap.  In the heap at the top of the page, we’d take off 23 (index 0), put 19 into the empty spot (into index 0 from index 2), then put 18 into the empty spot (into index 2 from index 5).  What do we put into index 5?  We can’t just move an adjacent value into that spot because it might not result in a valid maxheap.

We’ll prevent this problem by swapping the first & last elements in our maxheap.

To remove 23, we swap index 0 and 7.  We also decrement “nextPosition” so that while 23 is still in our array, it isn’t part of our maxheap.

0	1	2	3	4	5	6	7
7	20	19	12	10	18	14	23

This is not a valid heap (because 7 is smaller than both of its children: 20 and 19), so as long as it’s not valid, we swap the element with the larger of its two children.  Here we swap 7 and 20:

0	1	2	3	4	5	6	7
20	7	19	12	10	18	14	23

It’s still not valid (7 < 12 and 7 < 10) so we swap 7 and 12:

0	1	2	3	4	5	6	7
20	12	19	7	10	18	14	23

Now 7 is at index 3; it doesn’t have any children.  This process of moving an invalid top value from the top to closer to the bottom is handled in the code in the reheapDown method.

Notice now that 23 - the largest thing that was in our maxheap - is now in the last index.  If we were to remove 20, we’d swap 20 (index 0) with 14 (index 6), then swap 14 (index 0) with 19 (index 2), then swap 14 (index 2) with 18 (index 5).  Our new maxheap would look like this:

0	1	2	3	4	5	6	7
19	12	18	7	10	14	20	23

Notice now that the end of our array seems to be sorted.

This is the way the heapsort algorithm works - it’s basically just removing a bunch of things from our maxheap.

So, to complete a heapsort, first we create a maxheap from our array:

MaxHeap heap = new MaxHeap(array);

Then, all we have to do is remove everything from it.  The remove() method takes care of all of the sorting and your original array should now be sorted.