1.binary heap的实现

BinaryHeap.h

#ifndef BINARYHEAP_H
#define BINARYHEAP_H


class 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

#include "BinaryHeap.h"
#include <stdlib.h>

BinaryHeap::BinaryHeap(int N)
{
    this->N = 0;
    this->data = http://www.mamicode.com/(int *)malloc(sizeof(int)*(N+1));>
main.c
#include <iostream>
#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.各种排序算法的分析



Algorithm Part I:Priority Queues