The basic idea of Heap Sort is to sort with help of a special data structure called heap. A heap is a binary tree where each note in the tree contains a value. If the value of each node is no less than it's children, we call it a Max-Heap. If the value of each node is no more than it's children, we call it a Min-Heap.
Don't be confused by name heap, which is also used commonly as a notion of a region of memory space where program can dynamically allocate.
Heap is very interesting, on one hand, it's a binary tree, so it benefits binary tree properties such as it's height grows logarithmically with the number of nodes it has; on the other hand, it has one important order relationship between parent and child nodes.
As usual, we won't discuss in detail the theoretical aspect of the algorithm, instead, we focus on the implementation of the algorithm.
Before implementing the algorithm, let's first setup the unit test. As we already has our test infrastructure for previous sorting algorithms we discussed, we simply need to add some test cases inside.
For Heap Sort, I'm going to create a class with name HeapSort which provides a Sort method as other sort algorithms. So in the CppUnitTest/SortingTest.h, I add some test cases and their declarations:
CPPUNIT_TEST( testHeapSort_0 );
CPPUNIT_TEST( testHeapSort_1 );
...
void testHeapSort_0();
void testHeapSort_1();
Then I define those tests (methods) in the CppUnitTest/SortingTest.cpp:
void SortingTest::testHeapSort_0()
{
int iArray[] = {10, 5, 7, -2, 19, 50, 300, 320, 160, 1000};
std::vector v(iArray, iArray + sizeof(iArray) / sizeof(int));
HeapSort::Sort(v);
CPPUNIT_ASSERT_EQUAL(v[0], -2);
CPPUNIT_ASSERT_EQUAL(v[1], 5);
CPPUNIT_ASSERT_EQUAL(v[2], 7);
CPPUNIT_ASSERT_EQUAL(v[3], 10);
CPPUNIT_ASSERT_EQUAL(v[4], 19);
CPPUNIT_ASSERT_EQUAL(v[5], 50);
CPPUNIT_ASSERT_EQUAL(v[6], 160);
CPPUNIT_ASSERT_EQUAL(v[7], 300);
CPPUNIT_ASSERT_EQUAL(v[8], 320);
CPPUNIT_ASSERT_EQUAL(v[9], 1000);
}
void SortingTest::testHeapSort_1()
{
...
}
Now I can start coding the HeapSort class. First, I declare the main interface method, which is Sort for the HeapSort class, then I declare some helper methods Sort will use.
Same as described in the ITA, we will construct a binary tree directly on the input array, by using the index of an item in the array. So item 0 is always the root of the heap tree. Then, item 1 and 2 are two children of item 0, item 3 and 4 are two children of item 1, item 5 and 6 are children of item 2, and so on. In short, given a node
i , we know that it's left child is
2*i + 1 and it's right child is
(i + 1)*2 , if they exist, where
i starts from 0. As for it's parent, it depends. If
i = 0 , then it's the root node, so it does not really have a parent, otherwise, the parent node's index can be computed as
(i - 1)/2 .
We declare Parent, Left and Right methods to do the computation described above.
Also, the Heap Sort is based on first building a MaxHeap ( in case we need to sort non-decreasingly, otherwise, we build a MinHeap), then each time takes the root (which is the largest item in the heap), then reconstruct the heap. So we will also declare two auxiliary methods BuildMaxHeap and MaxHeapify to do the job. Methods for building and reconstructing MinHeap are also provided. The whole HeapSort class declaration looks like follows:
class HeapSort
{
public:
static void Sort(std::vector &v, bool bNonDecreasing = true);
protected:
static int Parent(const int i) { return ((i > 0) ? (i - 1) >> 1: 0); }
static int Left(const int i) { return (i << 1) + 1; }
static int Right(const int i) { return (i + 1) << 1; }
static void BuildMaxHeap(std::vector &v);
static void BuildMinHeap(std::vector &v);
static void MaxHeapify(std::vector &v, const int i, const int iHeapSize);
static void MinHeapify(std::vector &v, const int i, const int iHeapSize);
};Now comes the time to implement those methods. We will implement them in a bottom-up way. So, first look at the MaxHeapify method, it takes three parameters, a vector representing the heap (or a binary tree to be built to a heap) and a integer
i which is an index in the vector, representing a sub-tree rooted at
i . Also the heap size is provided as the third parameter. MaxHeapify assumes that two sub-trees rooted at both of
i 's children are already MaxHeaps, only
i is possibly violating the MaxHeap property. So the goal is just to make a MaxHeap rooted at
i . To this end, it simply recursively floats down the content of node
i until a proper place is found. "Float down" is just an exchange of
i with the maximum of
i , Left(
i ) and Right(
i ). Of cause, in case that the maximum is
i itself, nothing needs to be done. The code reads as follows:
void HeapSort::MaxHeapify(std::vector &v, const int i, const int iHeapSize)
{
int l = Left(i);
int r = Right(i);
int largest = i;
if ( l < iHeapSize && v[l] > v[i])
{
largest = l;
}
if ( r < iHeapSize && v[r] > v[largest])
{
largest = r;
}
if (largest != i)
{
int temp = v[largest];
v[largest] = v[i];
v[i] = temp;
MaxHeapify(v, largest, iHeapSize);
}
}
Next, we will implement BuildMaxHeap. With the help of MaxHeapify, this is fairly straightforward. We simply need to first MaxHeapify the sub-trees at the lowest level (actually the next to lowest, as the lowest are leaf nodes that does not have any child so trivially they are MaxHeap). As a result, we can start MaxHeapify the sub-trees from the middle of the vector. The trick is, given a vector of size
n , if we count from the end of the vector, the first item that may have a child always appears no early than the
n/2 th item (think why?). As a result, we have the following simply implementation of BuildMaxHeap:
void HeapSort::BuildMaxHeap(std::vector &v)
{
for (int i = (v.size() >> 1); i >= 0; i--)
{
MaxHeapify(v, i, v.size());
}
}
We can implement similar methods for MinHeap too.
Now that we have everything in hand, let's implement the final method Sort. We start by building a MaxHeap (or MinHeap), then each time, we exchange the root of the heap (item 0) with the last item in the heap. This exchange does two things: put the current largest at the end of the vector and put a smaller one at the heap root, breaking heap property. Then we use MaxHeapify to reconstruct the heap.
Once the heap is reconstructed, we have again the largest item at root, then we simply repeat the exchange-reconstruct. The code looks like the following, sorting by non-decreasing or non-increasing order are supported with parameter bNonDecreasing, as other sort algorithms:
void HeapSort::Sort(std::vector &v, bool bNonDecreasing)
{
if (v.size() <= 1 )
{
return;
}
if (bNonDecreasing)
{
BuildMaxHeap(v);
}
else
{
BuildMinHeap(v);
}
int iHeapSize = v.size();
for (int i = v.size() - 1; i >=1; i--)
{
int temp = v[0];
v[0] = v[i];
v[i] = temp;
iHeapSize--;
if (bNonDecreasing)
{
MaxHeapify(v, 0, iHeapSize);
}
else
{
MinHeapify(v, 0, iHeapSize);
}
}
}
ITA Reading Notes This document was generated using the
LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -html_version 4.0,math -no_navigation -scalable_fonts -split 0 -no_auto_link ITAReadingNotes-Main
The translation was initiated by Bing Han on 2011-11-20
Posts
