Heap and Heap Sort

Main Mirror Site http://www.jdxyw.com/?p=761

There is a convenient data structure named heap. Don't be confused with the heap concept in the memory management, which you use new or malloc to create a block memory. Actually, heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B), which implies that the item with the largest key would be always at the root of the tree. Such heap is called max heap. You also can create a min heap using the same way. You can construct priority queue using the head, which is a very useful data structure in many applicants, especially in the graph algorithms. There are some different types of heap, such as Fibonacci, Binary and Binomial. Here, I use the Binary as the example, which is the simplest one among them.

Common operations for Heap.

• Get the largest  key            O(1)
• Add/Insert a new key      O(logn)
• Pop the largest key            O(logn)
• Build a head from n keys O(nlogn)

Heaps are usually implemented using array. Below is the implementation using CPP.

I don't consider the re-size the heap, and do not use the template to support only type.

const int InitSize=30;

class Heap
{
public:
    Heap():HeapCpacity(InitSize),HeapSize(0)
    {}
    inline const int size() const
    {
        return HeapSize;
    }

    inline const int capacity() const
    {
        return HeapCpacity;
    }

    inline void swap(int x,int y)
    {
        int temp;
        temp=items[x];
        items[x]=items[y];
        items[y]=temp;
    }
    inline void add(int item)
    {
        ++HeapSize;
        items[HeapSize]=item;
        heapup(HeapSize);
    }

    inline int max()
    {
        return items[HeapSize];
    }

    int pop();

    virtual ~Heap(){}
private:
    int items[InitSize+1];
    int HeapCpacity;
    int HeapSize;
    void heapup(int index);
    void heapdown(int index);
};

void Heap::heapup(int index)
{
    if(index!=1)
    {
    int parent=index/2;
    int parentItem=items[parent];
    int childItem=items[index];
    if(childItem>parentItem)
        {
            swap(parent,index);
            heapup(parent);
        }
    }
}

void Heap::heapdown(int index)
{
    int left=index*2;
    int right=index*2+1;
    if(left>HeapSize)
        return;
    int largestIndex=index;
    if(left<=HeapSize && items[left]>items[index])
        largestIndex=left;

    if(right<=HeapSize && items[right]>items[index] &&  items[right]>  items[left])
        largestIndex=right;

    swap(index,largestIndex);
    if(largestIndex!=index)
        heapdown(largestIndex);
}

int Heap::pop()
{
    if(HeapSize>0)
    {
        int max=items[1];
        swap(1,HeapSize);
        HeapSize--;
        heapdown(1);
        return max;
    }
    else
        return -100000;
}

Heap can also be used in sorting field, which is the heap sort. The time complexity is O(nlogn). The process is below.

• Build a max-heap
• Switch the max item(the root item) with the last item in the array
• Detach the last item from the heap, which means the number of the item in the heap decreases one
• Re-construct the heap.(Use the heapdown function)
• Repeat step 2 to step 4 until there is no item in the heap.