ヒープの簡単な実現(擬似関数)
ヒープデータ構造は、完全に二叉ツリー構造と見なされる配列オブジェクトです.
最大ヒープ:各親ノードのは子供ノードより大きいです.
最小ヒープ:各親ノードのは子供ノードより小さいです.
積み上げ構造の二叉樹の保存は以下の通りです.
コードの実装は以下の通りです.
みなさんの貴重なご意見を歓迎します.
テストの用例は以下の通りです.
最大ヒープ:各親ノードのは子供ノードより大きいです.
最小ヒープ:各親ノードのは子供ノードより小さいです.
積み上げ構造の二叉樹の保存は以下の通りです.
コードの実装は以下の通りです.
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
//
template <typename T>
struct Greater
{
bool operator() (const T & l, const T & r)
{
return l > r;
}
};
template <typename T>
struct Less
{
bool operator() (const T & l, const T & r)
{
return l < r;
}
};
//
template <typename T,typename comer=Greater<T> >
class Heap
{
public:
//
Heap()
:_a(NULL)
{}
//
Heap(T * a, size_t size)
{
assert(a);
// vector
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//
for (int j = ((_a.size() - 2) / 2); j >= 0; j--)
{
//
_AdjustDown(j);
}
}
void Push(const T x)//
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);
}
void Pop()//
{
assert(_a.size() > 0);
swap(_a[0], _a[_a.size() - 1]);
_a.pop_back();
_AdjustDown(0);
}
size_t Size()
{
return _a.size();
}
bool Empty()
{
return _a.empty();
}
void print()
{
for (int i = 0; i < _a.size(); i++)
{
cout << _a[i] << " ";
}
cout << endl;
}
protected:
//
void _AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
comer com;
while (child < _a.size())
{
//
if (child + 1 < _a.size() && com(_a[child + 1] , _a[child]))
{
child++;
}
//
if (com (_a[child],_a[parent]))
{
swap(_a[child], _a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//
void _AdjustUp(size_t child)
{
assert(child < _a.size());
int parent = (child - 1) / 2;
comer com;
while (child > 0)
{
// <
if (com(_a[child], _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
private:
vector <T> _a;
};みなさんの貴重なご意見を歓迎します.
テストの用例は以下の通りです.
void Test()
{
int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
Heap<int,Less<int> > hp1(a, sizeof(a) / sizeof(a[0]));
hp1.print();
cout << hp1.Size() << endl;
cout << hp1.Empty() << endl;
hp1.Push(20);
hp1.print();
cout << hp1.Size() << endl;
cout << hp1.Empty() << endl;
hp1.Pop();
hp1.print();
cout << hp1.Size() << endl;
cout << hp1.Empty() << endl;