1.binary heap实现

BinaryHeap.h

#ifndef BINARYHEAP_H#define BINARYHEAP_Hclass BinaryHeap{    public:        BinaryHeap(int N);        bool isEmpty();        void exchange(int i,int j);        void insert(int key);        int delMax();        int getMax();        virtual ~BinaryHeap();    protected:    private:        int N;        int * data;        void swim(int key);        void sink(int key);};#endif // BINARYHEAP_H

BinaryHeap.cpp

#include "BinaryHeap.h"#include 
     
      BinaryHeap::BinaryHeap(int N){    this->N = 0;    this->data = (int *)malloc(sizeof(int)*(N+1));}BinaryHeap::~BinaryHeap(){}bool BinaryHeap::isEmpty(){    return N == 0;}void BinaryHeap::exchange(int i,int j){    int temp = this->data[i];    this->data[i] = this->data[j];    this->data[j] = temp;}void BinaryHeap::swim(int key){    while(key > 1 && data[key/2] < data[key])    {        exchange(key/2,key);        key = key/2;    }}void BinaryHeap::insert(int key){    N++;    data[N] = key;    swim(N);}void BinaryHeap::sink(int key){    while(key*2 <= N)    {        int j = key*2;        if(j < N && data[j] < data[j+1])            j++;        if(data[key] >= data[j])            break;        else        {            exchange(key,j);            key = j;        }    }}int BinaryHeap::delMax(){    int max = data[1];    exchange(1,N-1);    N--;    sink(1);    return max;}int BinaryHeap::getMax(){    return data[1];}
     

main.c

#include 
     
      #include "BinaryHeap.h"using namespace std;int main(){    BinaryHeap * bp = new BinaryHeap(10);    bp->insert(3);    bp->insert(2);    bp->insert(1);    bp->insert(5);    bp->insert(8);    bp->insert(7);    cout << bp->getMax() << "\n";    bp->delMax();    cout << bp->getMax() << "\n";    char c;    cin >> c;    return 0;}
     

各操作时间复杂度的分析：

2.堆排序

堆排序的主要步骤：

（1）建堆

（2）依次移除最大元素，将它放到数组的尾端。

3.各种排序算法的分析

版权声明：本文博客原创文章，博客，未经同意，不得转载。