// 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)  //  左子樹和右子樹的最小值和節(jié)點值比較，將最小值壓入節(jié)點，繼續(xù)尋找適合節(jié)點值的位置
            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;
}

標簽：

版權申明：本站文章部分自網絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。