// 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;
}
以上就是短码网小编为大家整理的《C++STL之二叉堆》相关内容,希望大家喜欢。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若内容造成侵权/违法违规/事实不符,请将联系本站反馈,一经查实,立即处理!
《C++STL之二叉堆》文档下载仅供参考学习,下载后请在24小时内删除。
转载注明出处:https://www.duanma.net/article/76c943d5228.html