// myBinaryHeap.cpp : 定義控制臺應用程序的入口點。
//

include "stdafx.h"
include <vector>
include <iostream>
define  random(x) (rand()%x)
using namespace std;
template <typename T>
class BinaryHeap
{
private:
    int currentSize;
    vector<T> vecArray;
    void buildHeap()    //將序列建堆的過程
    {
        for (int i = currentSize/2 ; i >= 0; i--) 
        {
            perColateDown(i);
        }
    };
    void perColateDown(int hole);
public:
    explicit BinaryHeap(int capacity = 100){currentSize = capacity;}
    explicit BinaryHeap (const vector<T>& items):vecArray(items.size() + 10), currentSize(items.size())  //------vecArray(items.size() + 10)
    {
        for (int i = 0; i < items.size() ; i++)
        {
            vecArray[i] = items[i];
        }
        buildHeap();
    }

bool isEmpty() const
{
    return  0== currentSize;
};
const T& findMin() const
{
    return vecArray[0];
}
const vector<T> getVector()
{
    return vecArray;
}

void insert(const T& x);
void deleteMin();
void deleteMin(T& minItem);
void makeEmpty();

};
template <typename T>
void BinaryHeap<T>::insert(const T& x)
{
    if (currentSize == vecArray.size() - 1)
    {
        vecArray.resize(vecArray.size() * 2);
    }
    int hole = ++ currentSize; //建立一個空穴，即數組的一個下標
    for (; hole > 1 && x< vecArray[hole/2]; hole << 1)
    {
        vecArray[hole] = vecArray[hole/2];
    }
    vecArray[hole] = x;
}
template <typename T>
void BinaryHeap<T>::deleteMin()
{
    if (isEmpty()){    return;}
    vecArray[1] = vecArray[currentSize --];
    perColateDown(1);
}
template <typename T>
void BinaryHeap<T>::deleteMin(T& minItem)
{
    if (isEmpty()){    return;}
    minItem = vecArray[1] ;
    vecArray[1] = vecArray[currentSize --];
    perColateDown(1);
}
template <typename T>
void BinaryHeap<T>::perColateDown(int hole)   //向下計算當前數的實際位置
{
    int child ; 
    T temp = vecArray[hole];
    for(; hole2 < currentSize; hole = child)
    {
        child = hole  2;
        if (child != currentSize && vecArray[child+1] < vecArray[child])  // 若左子樹大于右子樹
            child ++;
        if (vecArray[child] < temp)  //  左子樹和右子樹的最小值和節點值比較，將最小值壓入節點，繼續尋找適合節點值的位置
            vecArray[hole] = vecArray[child];
        else
            break;
    }
    vecArray[hole] = temp;
}
int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> vecInt;
    for (int i = 0; i < 10; i++)
    {
        vecInt.push_back(random(51));
        cout << vecInt[i] <<" ";
    }

cout  <<endl;
BinaryHeap<int>* bh =new BinaryHeap<int>(vecInt) ;
for (int i=0; i < 10; i++)    
{
    cout << bh->getVector()[i] <<" ";   //這里等于實現了堆排序算法
}
return 0;

}</pre>