Inserting letters onto an empty heap

Question

I'm trying to insert "KONTINUASJONSEKSAMEN" onto an empty heap. The result is supposed to produce "USTSOSNOMNJNNEKAAKEI", which I'm not capable of. I end up with "UTSSOONSMNJNNEKAAKEI" which I work out from the visualization under.

                                 U
                             /        \  
                            T           S 
                         /    \       /   \    
                       S       O     O     N
                     /  \     / \   / \   / \ 
                    S    M    N  J  N  N E   K
                   / \   /\   /
                  A  A   K E I    

I start with the first K at the top, going downwards, left to right with the rest of the word, switching around lower value parents with higher value children. Where higher value means closer to Z.

Do you see where I'm going wrong?

Answer 1

I think the problem is that you're doing insertion top-down, and that heap was built by doing insertion from the bottom up. I used my own heap implementation that does bottom-up insertion, and the heap that results from that input string is exactly what your expected output is.

If you're doing a top-down insertion in a binary heap, then there is ambiguity when you encounter this situation:

    K
  S   S
 A B C D

That is, the node you're inserting is smaller than both of its children, and both of the children are equal.

Which 'S' do you pick to swap with? If you always pick the one on the left, and somebody else always picks the one on the right, then the resulting heaps can be wildly different. For example:

    S           S
  K   S       S   K
 A B C D     A B C D

Both are valid heaps.

Typically, heap insertion is done by adding the new node as the last node of the heap, and then bubbling it up the tree to its proper position. So, if you start with K at the root and add O, you have:

  K
 O

You note that O is larger than K, so you swap the nodes to give you:

  O
 K

Then you add N and get

  O
 K N

You first add T as the last node of the heap, and bubble it up:

   O
 K   N
T

T is greater than K, so you swap the nodes:

   O
 T   N
K

And T is greater than O, so you swap them:

   T
 O   N
K

Doing insertion bottom-up this way, there is no ambiguity.

You should also note that bottom-up insertion is more efficient than top-down insertion. If you insert at the top, then it always takes log₂(n) iterations, where n is the number of items currently in the heap. Even if the new item replaces the root, you have to sift things down until you have a new entry at the leaf level.

When you do bottom-up insertion by first putting the new node at the leaf level, half the time the node will stay at the leaf level. And 75% of the time the node won't go up more than one level. The only time you have to do log₂(n) swaps is when the new item replaces the root. There is a good argument to be made that binary heap insertion is O(1), but that assumes bottom-up insertion. See Argument for O(1) average-case complexity of heap insertion for details.

For more information about how to implement bottom-up insertion, see my blog series on heaps at http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/.

Answer 2

I found a quick way through it. Instead of typing and erasing endless trees with leaves I set the characters up in an array, drawing a line for every 1st, 2nd, 4th, 8th, 16th... character. The character(s) to the left of the helpline(s) are the parent(s) to adjacent characters right of the helpline. Character 1 is parent to 2 and 3. Character 2 is parent to 4 and 5 and so on. Again I tested if left child was larger than parent, if so they switch (noted the switch in my workbook/excel doc directly under the previous parent/child). And I checked then the right child against the (new) parent. Attaching a screenshot of my excel doc.