算法导论之堆排序

garyneville

                就贴代码了。Ubuntu 9.04,gcc 4.3.3 下运行成功。
#ifndef HEAP_H_
#define HEAP_H_
#includevector>
#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
#includestdlib.h>
#includestdio.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; iarray_length ; ++i)
    {
        m_array = array;
    }
}
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);
    }   
    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;
    m_array = 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;
}
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/72023/showart_2072752.html