算法导论之堆排序

就贴代码了。Ubuntu 9.04,gcc 4.3.3 下运行成功。

#ifndef HEAP_H_
#define HEAP_H_
#include<vector>
#define MAX_LEN 100
using namespace std;

class Heap{
public:
    Heap(int heap_size,int array_length,int *array);
    ~Heap();
    void max_heapify(int pos);
    void build_max_heap();
    void sort();
    int parent(int pos){return (pos-1)/2;}
    int right(int pos){return 2*pos+1;}
    int left(int pos){return 2*pos+2;}
    void display();    
    void exchange(int i,int j);
private:
    int m_heap_size ;
    int m_array_length;
    int *m_array;
};


#endif


#include<stdlib.h>
#include<stdio.h>
#include "heap.h"
Heap::Heap(int heap_size,int array_length,int *array)
{
    m_heap_size = heap_size ;
    m_array_length = array_length;
    m_array = new int[array_length];
    for(int i=0; i<array_length ; ++i)
    {
        m_array[i] = array[i];
    }
}

Heap::~Heap()
{
    delete [] m_array;
    m_array = NULL;    
}


void Heap::max_heapify(int pos)
{
    
    int largest ,tmp_value ;
    int right_pos = right(pos);
    int left_pos = left(pos);
    if(right_pos<=m_heap_size-1 && m_array[right_pos]>m_array[pos])
        largest = right_pos;    
    else
        largest = pos;
    if(left_pos<=m_heap_size-1 && m_array[left_pos]>m_array[largest])
        largest = left_pos;
    if(largest!=pos)
    {
        exchange(largest,pos);
        max_heapify(largest);
    }
}

void Heap::build_max_heap()
{
    m_heap_size = m_array_length ;
    for(int i = (m_heap_size - 1) / 2 ; i >=0 ; --i)
    {
        max_heapify(i);
    }
}
void Heap::sort()
{
    build_max_heap();
    for(int i = m_array_length-1; i>=0 ; --i)
    {
        exchange(0,i);    
        m_heap_size--;
        max_heapify(0);
    }    
}

void Heap::display()
{
    for(int i = 0 ; i < m_array_length ; ++i)
    {
        printf("%d\t",m_array[i]);
    }    
    printf("\n");
}
void Heap::exchange(int i,int j)
{
    if(i > m_heap_size || j > m_heap_size)
    {
        fprintf(stderr,"Over Heap\n");
        return ;
    }
    int tmp = m_array[j];
    m_array[j] = m_array[i];
    m_array[i] = tmp;
}

int main(int argc,char **argv)
{
    int array[10] = {1,2,3,4,54,6,7,8,9,10};
    Heap *heap = new Heap(10,10,array);
    heap->build_max_heap();
    heap->sort();
    heap->display();
    delete heap;
    return EXIT_SUCCESS;
}