// 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(; hole*2 < 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;
}