数据结构堆（代码ampampamp测试结果）

　　#include ＂pch.h＂
　　#include
　　#include
　　#include
　　#include
　　using namespace std;
　　void pushHeap(vector& v)
　　{
　　int currentPos, parentPos;
　　int target, last = v.size();
　　currentPos = last - 1;
　　parentPos = (currentPos - 1) / 2;
　　target = v[last - 1];
　　while (currentPos != 0)
　　{
　　if (target > v[parentPos])
　　{
　　v[currentPos] = v[parentPos];
　　currentPos = parentPos;
　　parentPos = (currentPos - 1) / 2;
　　}
　　else break;
　　}
　　v[currentPos] = target;
　　}
　　void pushHeap2(vector& v)
　　{
　　int currentPos, parentPos;
　　int target, last = v.size();
　　currentPos = last - 1;
　　parentPos = (currentPos - 1) / 2;
　　target = v[last - 1];
　　while (currentPos != 0)
　　{
　　if (target < v[parentPos])
　　{
　　v[currentPos] = v[parentPos];
　　currentPos = parentPos;
　　parentPos = (currentPos - 1) / 2;
　　}
　　else break;
　　}
　　v[currentPos] = target;
　　}
　　bool Compare(int a1,int a2)
　　{
　　if (a1 > a2)
　　{
　　return true;
　　}
　　else
　　{
　　return false;
　　}
　　}
　　bool Compare2(int a1, int a2)
　　{
　　if (a1 < a2)
　　{
　　return true;
　　}
　　else
　　{
　　return false;
　　}
　　}
　　void adjustHeap1(vector& v, int first, int last)
　　{
　　int currentPos, childPos;
　　int target;
　　currentPos = first;
　　target = v[first];
　　childPos = 2 * currentPos + 1;
　　while (childPos <= last - 1)
　　{
　　if ((childPos + 1 <= last - 1) && Compare(v[childPos + 1], v[childPos]))
　　childPos = childPos + 1;
　　if (Compare(v[childPos], target))
　　{
　　v[currentPos] = v[childPos];
　　currentPos = childPos;
　　childPos = 2 * currentPos + 1;
　　}
　　else break;
　　}
　　v[currentPos] = target;
　　}
　　void adjustHeap2(vector& v, int first, int last)
　　{
　　int currentPos, childPos;
　　int target;
　　currentPos = first;
　　target = v[first];
　　childPos = 2 * currentPos +1;
　　while (childPos <= last - 1)
　　{
　　if ((childPos + 1 <= last - 1) && Compare2(v[childPos + 1], v[childPos]))
　　childPos = childPos + 1;
　　if (Compare2(v[childPos], target))
　　{
　　v[currentPos] = v[childPos];
　　currentPos = childPos;
　　childPos = 2 * currentPos + 1;
　　}
　　//if ((childPos + 1 >= last - 1) && Compare2(v[childPos + 1], v[childPos]))
　　//childPos = childPos + 1;
　　else break;
　　}
　　v[currentPos] = target;
　　}
　　void popHeap1(vector& v)
　　{
　　if (v.size() <= 0)
　　{
　　return;
　　}
　　int size = v.size();
　　swap(v[0], v[size - 1]);
　　adjustHeap1(v, 0, size -1);
　　v.pop_back();
　　}
　　void popHeap2(vector& v)
　　{
　　if (v.size() <= 0)
　　{
　　return;
　　}
　　int size = v.size();
　　swap(v[0], v[size - 1]);
　　adjustHeap2(v, 0, size - 1);
　　v.pop_back();
　　}
　　int main()
　　{
　　vectorv;
　　srand(int(time(0)));
　　for (int i = 0; i < 10; i++)
　　{
　　v.push_back(rand()%100);
　　pushHeap2(v);
　　}
　　cout << ＂最小堆展示:＂ << endl;
　　for (int i = 0; i < v.size(); i++)
　　{
　　cout << v[i] << ＂ ＂;
　　}
　　cout << endl;
　　cout << ＂删除掉一个元素后的最小堆：＂ << endl;
　　popHeap2(v);
　　for (int i = 0; i < v.size(); i++)
　　{
　　cout << v[i] << ＂ ＂;
　　}
　　cout << ＂ -----------------------------------------------＂ << endl;
　　vectorv2;
　　for (int i = 0; i < 1000000; i++)
　　{
　　v2.push_back(rand());
　　pushHeap2(v2);
　　if (v2.size() > 10)
　　{
　　popHeap2(v2);
　　}
　　}
　　cout << ＂一百万个数据最小堆的结果:＂ << endl;
　　for (int i = 0; i < v2.size(); i++)
　　{
　　cout << v2[i] <<＂ ＂;
　　}
　　cout << endl;
　　}
　　测试结果