Heapsort: Part Two

November 12, 2014 by Leave a Comment

HeapsortIn the previous article, we introduced the heapsort algorithm and coded several helper functions in Python. In this article, we will finally code the heapsort function and test it on some input data.

To recap, we already introduced the following functions:

  • heapify: Turns a list into a binary heap.
  • rebuildHeap: Accepts as input a heap with the root node deleted and rebuilds the heap.
  • consolidateHeap: Moves all empty nodes to the bottom of the heap so we can shrink the heap.
  • swap: Swaps the contents of two variables.

Since we did all the heavy lifting in writing the helper functions, coding heapSort is rather simple:

def heapSort(L):
   '''Given a list, perform a binary sort on it
   '''
   # First, reconstitute list as a binary heap: 
   heapify(L)
   high = len(L)
   # While there is still data in the heap,
   # remove the root node, rebuild and
   # consolidate the heap, and move the old
   # root node to the end
   while high > 0:
      # Delete root node; save in temp
      temp = L[0]
      L[0] = None
      # Rebuild and consolidate heap
      rebuildHeap(L,0,high)
      consolidateHeap(L,high)
      high -= 1
      # Move old root node to end
      L[high] = temp

As you can see, once we create the heap, all we are doing is [1] deleting the root node from the heap by setting its value to “None”; [2] rebuild the heap and consolidate the heap; [3] decrement the variable indicating the size of the heap; [4] move the old root node back into the list right after the heap; [5] repeat until the heap size is 0. You may have noticed that when we call rebuildHeap and consolidateHeap, we specify the size of the heap. This is to ensure the sorted list which we are inserting at the end of the list is not treated as part of the heap.

To test our heapsort function, I reused the list from the previous article, and used the following code:

>>> myList = [123,79,29,997,519,17,239,144,51,372]
>>> heapSort(myList)
>>> print(myList)
[17, 29, 51, 79, 123, 144, 239, 372, 519, 997]

As you can see, the heapsort function seems to work, and has the added advantage (over merge sort) of supporting the ability to sort in place. In the next article, we’ll examine one more efficient sorting algorithm: quicksort.

The source code for this heapsort implementation can be found here.

External Links:

Heapsort on Wikipedia

Filed Under: Tutorials Tagged With: , ,

Heapsort: Part One

November 7, 2014 by Leave a Comment

 

 

HeapsortIn the previous article, we applied the concept of recursion to implementing an efficient sorting algorithm (merge sort). In this article, we will apply our knowledge of Python to a different sorting algorithm: the heapsort.

Heapsort involves taking an unsorted list and first forming a binary heap from the list. A binary heap is a data structure in which each node has at most two child nodes. The parent node is always greater than either child node. Therefore, the root node (the only node that is not a child of any node) must be greater than any other node. We can thus sort the list by removing the root node from the heap and then rebuilding the heap, which is now one item smaller. We can insert the deleted root node after the heap, and thus sort the list in place.

We are going to need several functions in order to make this all work:

  1. The main heapSort function.
  2. A helper function to generate the binary heap.
  3. A helper function to rebuild the binary heap after we delete the root node.

The pseudocode for heapsort looks like this:

heapsort(myList):
   heapify(myList)
   high = len(myList)
   while high > 0:
      temp = myList[0]
      rebuildHeap(myList)
      high -= 1
      myList[high] = temp

Implementing Heapsort: The heapify Function

The heapify function, which simply creates a binary heap from a list of items, is easy to code, so perhaps we should start with it:

def heapify(L,root=0):
   # Given a list and the index of the root node,
   # form a heap (for heapsort)
   if len(L)-root-1 > 0:
      lnode = root*2+1
   i = lnode
   nsiblings = 2
   while i < len(L): if i + nsiblings > len(L):
      nsiblings = len(L)-i
      for j in range(i,i+nsiblings):
      if L[root] < L[j]:
         swap(L,root,j)
      i = i*2+1
      nsiblings *= 2
      if lnode < len(L):
         heapify(L,lnode)
      if lnode+1 < len(L): 
         heapify(L,lnode+1)

As simple as it is, we’re probably going to do a lot more swap operations, so I decided to make a function for it:

def swap(L,x,y): 
   # Swap two items 
   temp = L[x] 
   L[x] = L[y] 
   L[y] = temp

This code does not require much explanation. The heapify function takes two arguments: a list and the index of the root node (default value is 0). If the difference between the first and last index is less than or equal to zero, then there are less than two list entries, and the input list is already a binary heap. If not, we iterate through the remaining items, starting with the left and right child nodes, then moving on to the children of those nodes, and so on, skipping the nodes that are not children of the root node. When we are done, the correct value is in the root node, and all that remains to be done is to apply the function recursively to the left node (lnode) and the right node (lnode+1). It’s good practice to test each function individually, so let’s provide some test input for heapify:

>>> mylist = [1,2,3,4,5,6,7,8,9,10]
>>> heapify(mylist)
>>> mylist
[10, 9, 6, 7, 8, 2, 5, 1, 4, 3]
>>>

If we represent this heap graphically, we can confirm that it is a valid binary heap:

     10
    /  \
   9    6
  /\   / \
 7  8  2  5
 /\ /
1 4 3

Implementing Heapsort: rebuildHeap and consolidateHeap

We could write our heapsort algorithm by just removing the root node from the heap and running heapify on the remaining items. That would require many more operations, however than is necessary. Instead, we will write a separate rebuildHeap function that does the following:

  1. Make the higher-valued child node the new root node.
  2. If the left node was promoted, run rebuildHeap recursively on the left node. If the right node was promoted, run rebuildHeap recursively on the right node.

You are probably wondering how we are going to denote a deleted node. Fortunately, Python has the built-in value “None” which is essentially the Python equivalent of NULL. If we want to delete a node, we will change its value to None:

>>> mylist[0] = None

This deletes the root node of the heap, and we now must rebuild the heap. Now is a good time to introduce the rebuildHeap function:

def rebuildHeap(L,root=0,size=-1):
   '''Given a heap with the root node deleted,
   restore the heap (for heapsort)'''
   if size == -1:
      size = len(L)
   lnode = root*2+1
   if size-root-1 > 0 and lnode < size: 
      # If right node does not exist or left node 
      # is greater than right node, promote left 
      # node 
      if lnode + 1 >= size or L[lnode] >= L[lnode+1]:
         L[root] = L[lnode]
         L[lnode] = None
         rebuildHeap(L,lnode,size)
      # Else if right node exists, promote right node
      elif lnode+1 < size:
         L[root] = L[lnode+1]
         L[lnode+1] = None
         rebuildHeap(L,lnode+1,size)

The rebuildHeap function is even simpler than the heapify function. We take three arguments: the list, the index of the parent node, and the size of the list. We provide default values for parent and size, so if we just want to rebuild the entire heap, we just need to specify the list. If the heap has at least 2 items, we promote the left node if either [1] there is no right node or [2] its value is greater than the right node. Otherwise, if the right node exists, we promote the right node. In either case, we have disturbed the heap integrity on one side by promoting a node, so we run the function recursively on whichever side we promoted. Note that whenever we promote a node, we leave a node with a value of “None” in its place, and at the end, we will have a childless node with a value of “None” as a placeholder.

We now have functions to both create a heap and rebuild the heap, but we don’t have any means of shrinking the heap. This is unfortunate, as we really want to be able to sort the list in place, and insert entries after the heap. But we cannot do this, because the empty nodes are not always at the end of the heap. We can illustrate the problem by running the following code:

myList = [123,79,29,997,519,17,239,144,51,372]
heapify(myList)
print(myList)
while myList[0] != None:
myList[0] = None
rebuildHeap(myList)
print(myList)

This code creates a list, turns it into a binary heap and prints out the initial heap. On each pass through the loop, we delete the root node, then rebuild the heap and print the results until there is nothing left in the heap. Running this code yields the following result:

[997, 519, 239, 144, 372, 17, 29, 79, 51, 123]
[519, 372, 239, 144, 123, 17, 29, 79, 51, None]
[372, 144, 239, 79, 123, 17, 29, None, 51, None]
[239, 144, 29, 79, 123, 17, None, None, 51, None]
[144, 123, 29, 79, None, 17, None, None, 51, None]
[123, 79, 29, 51, None, 17, None, None, None, None]
[79, 51, 29, None, None, 17, None, None, None, None]
[51, None, 29, None, None, 17, None, None, None, None]
[29, None, 17, None, None, None, None, None, None, None]
[17, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None]

As you can see, the empty nodes are interspersed with valid data. We need a means of consolidating the heap. The consolidation routine for our heapsort algorithm involves the following:

  1. Starting at the end of the heap, look for an empty node.
  2. If an empty node is found, start at the end of the heap and look for a valid node.
  3. Swap the empty and valid node.
  4. Check if the valid node’s new parent’s value is less than that of the newly-moved node. If so, swap them and repeat the process of comparing the parent’s value to the child’s, substituting the new parent node. Continue until the child is less than parent or we have reached the root node.
  5. Repeat the entire process until there are no more nodes to check.
def consolidateHeap(L,size=-1):
   '''Consolidate nodes in the
   heap; swap where necessary (for heapsort)'''
   if size == -1:
      size = len(L)
   i = size-2
   while i > 0:
      # Check for empty nodes
      if L[i] == None:
         child = i
         j = size-1
         # Find the last non-empty node
         # in the heap and swap
         while L[j] == None and j > 0:
            j -= 1
         if (j > 0):
            swap(L,child,j)
         # Maintain heap integrity by swapping
         # parent and child nodes if necessary
         parent = int((child-1)/2)
         while parent > 0 and L[parent] < L[child]:
            swap(L,parent,child)
            child = parent
            parent = int((child-1)/2)
      i -= 1

This function is a little more complex than the others, but running our test with the consolidateHeap function inserted after rebuildHeap yields the following result:

[997, 519, 239, 144, 372, 17, 29, 79, 51, 123]
[519, 372, 239, 144, 123, 17, 29, 79, 51, None]
[372, 144, 239, 79, 123, 17, 29, 51, None, None]
[239, 144, 51, 79, 123, 17, 29, None, None, None]
[144, 123, 51, 79, 29, 17, None, None, None, None]
[123, 79, 51, 29, 17, None, None, None, None, None]
[79, 29, 51, 17, None, None, None, None, None, None]
[51, 29, 17, None, None, None, None, None, None, None]
[29, 17, None, None, None, None, None, None, None, None]
[17, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None]

Thus, the consolidateHeap function does what it is supposed to do, and we can sort in place with heapsort. In the next article, we will use these functions together to implement heapsort.

External Links:

Heapsort on Wikipedia

Filed Under: Tutorials Tagged With: , , , ,