スタックの構造分析と応用
二叉樹では、二叉樹、一つはチェーン表、一つは配列ですが、配列は満二叉樹または完全二叉樹に比較的適しています.
ヒープデータ構造は、完全に二叉ツリー構造と見なされる配列オブジェクトです.
積み上げ構造の二叉樹は二つの方法があります.
最大ヒープ:各親ノードのは子供ノードより大きいです.
最小ヒープ:各親ノードのは子供ノードより小さいです.
擬似関数
擬似関数とは、クラスを関数のように見えるように使うことで、クラスの中で一つのoperatorを実現することです.
テスト
1.積み上げ順序
分析:山のように或いは山のように並べてから、各小さい木は山のように或いは小さい山のようにしか保証できないので、配列要素を完全に順番に並べられないように並べられます.
だから、私たちはまず山のように並べてから、山の頂の元素を大要素にして、順番に山の頂の元素と未交換の最後の元素を交換して、交換が終わったら、大きな元素以外の元素を交換します.
分析:小さい山を作って前のK個の元素を保管して、小さい山の頂の元素は前のKの中で最小の値で、残りのN-K個の数の中で順次と山の頂の元素を積み上げて比較して、もし山の頂の元素より大きいならば、山に積んでごとに1つの元素を更に小さい山に並べ替えて、山の頂の元素をいつもこのK元素の最小の値にさせます.スタックトップの要素より小さい場合は、次の数の比較を続けます.N−K個の要素を全部比較し終わったとき、このK個の要素は最大の前K個の数である.
ヒープデータ構造は、完全に二叉ツリー構造と見なされる配列オブジェクトです.
積み上げ構造の二叉樹は二つの方法があります.
最大ヒープ:各親ノードのは子供ノードより大きいです.
最小ヒープ:各親ノードのは子供ノードより小さいです.
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
Heap()//
{}
Heap(T *a, size_t size)//
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
// ，
// ， ：
// = *2+1
// = *2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)// （ ）
{
_AdjustDown(j);
}
/*
j size_t ， j
j>=0 ，
*/
}
public:
void Push(const T &x)//
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);// ， （ x ）
}
void Pop()// （ ）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//
_a.pop_back();//
_AdjustDown(0);//
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)// O(log2(N))
{
size_t child = parent * 2 + 1; //
while (child < _a.size())
{
if ((child + 1) < _a.size() && _a[child] < _a[child + 1])// （ ）
{
++child;//
}
if (_a[child]>_a[parent])// ，
{
swap(_a[child], _a[parent]);
parent = child;//
child = parent * 2 + 1;//
}
else
break;
}
}
void _AdjustUp(size_t child)// O(log2(N))
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_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] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int> h1(a, 10);
h1.Push(3);
h1.Push(4);
h1.Print();
h1.Push(100);
h1.Print();
h1.Pop();
h1.Print();
h1.Pop();
h1.Print();
}
int main()
{
test();
getchar();
return 0;
}擬似関数
擬似関数とは、クラスを関数のように見えるように使うことで、クラスの中で一つのoperatorを実現することです.
struct Free{ void operator()(void *ptr) { free( ptr); }};void Testsharedptr(){ int *p1=(int*)malloc(sizeof(int)*10); shared_ptr<int>sp1(p1,Free());// p1}アナログ関数で最大山と最小山を実現します.template<class T>
struct Less
{
bool operator()(const T&left, const T&right)
{
return left < right;
}
};
template<class T>
struct Greater
{
bool operator()(const T&left, const T&right)
{
return left>right;
}
};
template<class T,class compare=Greater<T>>
class Heap
{
public:
Heap()//
{}
Heap(T *a, size_t size)//
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
// ，
// ， ：
// = *2+1
// = *2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)// （ ）
{
_AdjustDown(j);
}
}
public:
void Push(const T &x)//
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);// ， （ x ）
}
void Pop()// （ ）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//
_a.pop_back();//
_AdjustDown(0);//
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)// O(log2(N))
{
size_t child = parent * 2 + 1; //
compare 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)// O(log2(N))
{
size_t parent = (child - 1) / 2;
compare 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 test1()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int,Less<int>> h1(a, 10);//
h1.Push(3);
h1.Push(4);
h1.Print();
h1.Push(100);
h1.Print();
h1.Pop();
h1.Print();
h1.Pop();
h1.Print();
Heap<int>h2(b);//
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
}1.積み上げ順序
分析:山のように或いは山のように並べてから、各小さい木は山のように或いは小さい山のようにしか保証できないので、配列要素を完全に順番に並べられないように並べられます.
だから、私たちはまず山のように並べてから、山の頂の元素を大要素にして、順番に山の頂の元素と未交換の最後の元素を交換して、交換が終わったら、大きな元素以外の元素を交換します.
/******************************
，
*/
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child]<a[child + 1]&&child+1<size)
{
child++;
}
if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int *a, int n)
{
assert(a);
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a,i,n);//
}
for (int i = 0; i < n; i++)
{
swap(a[n - 1 - i],a[0]);
AdjustDown(a, 0, n - 1 - i);
}
}分析:小さい山を作って前のK個の元素を保管して、小さい山の頂の元素は前のKの中で最小の値で、残りのN-K個の数の中で順次と山の頂の元素を積み上げて比較して、もし山の頂の元素より大きいならば、山に積んでごとに1つの元素を更に小さい山に並べ替えて、山の頂の元素をいつもこのK元素の最小の値にさせます.スタックトップの要素より小さい場合は、次の数の比較を続けます.N−K個の要素を全部比較し終わったとき、このK個の要素は最大の前K個の数である.
/*
N K
， K, N-K
*/
const int N = 1000000;
const int K = 100;
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child <size)
{
if (child+1<size&&a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void GetTopK(int *a)
{
assert(K < N);
int top[100];
for (size_t i = 0; i < 100; i++)
{
top[i] = a[i];
}
// ，
for (int i = (K - 2) / 2; i>=0; i--)
{
AdjustDown(top, i, K);
}
// N-K ， ，
for (size_t j = K; j < N ; j++)
{
if (a[j]<top[0])
{
top[0] = a[j];
AdjustDown(top, 0, K);
}
}
}