ヒープの作成&ヒープの並べ替え&ヒープの応用

ヒープの作成

積み上げるのは実は1種の完全な二叉の木で、積み上げるのは山ほどと小さいヒープに分けて、Key[i]>Key[2 i＋1]とKey[i]>Key[2 i+2]を満たす時は山のように積み上げられています.

#pragma once
#include
#include
#include
using namespace std;
template
class Heap
{
public:
    Heap()
        :_a(NULL)
    {}

    Heap(const T* a,size_t size)
    {
        assert(a);
        for(size_t i=0;i0;--i)
        {
            _AdjustDown(i);
        }
    }
    void Push(const T& x)
    {
        _a.push_back(x);
        _AjustUp(_a.size()-1);
    }
    void Pop()
    {
        assert(_a.empty());
        swap(_a[0],_a[a.size()-1]);
        _AdjustDown();
    }
protected:
    void _AdjustDown(size_t parent)
    {
        size_t child = parent*2+1;
        while(child > 0)
        {
            if(_a[child] _a[parent])   //        
            {
                swap(_a[child],_a[parent]);
                parent = child;
                child = parent*2+1;
            }
            else 
            {
                break;
            }
        }
    }
    void _AjustUp(size_t child)
    {    
        int parent =  (child-1)/2;
        while(child > 0)  //          ，     。         ，    size_t  int
        {
            if(_a[parent]<_a protected:=""> _a;
};
void TestHeap()
{
    int a[] = {10,11,13,12,16,18,15,17,14,19};
    Heap Hp1(a,sizeof(a)/sizeof(a[0]));
    Hp1.Push(20);
}
int main()
{
     TestHeap();
    system( "pause");
    return 0;
}

2.積み上げ思想
大きな根の山の小さな根の山の頂の元素を利用するのは最大の記録(最小の記録)で、毎回無秩序の中から最大(最小の記録)を選ぶのが簡単になりました.ここでは大きな根を使って思想を積み、
1)最初の並べ替え待ちキーワードのシーケンス(R 1,R 2….Rn)を大一番上の山に構築し、この山は初期の無秩序領域である.
2)スタックトップ要素R[1]と最後の要素R[n]を交換すると、新しい無秩序エリア(R 1,R 2,・・・Rn-1)と新しい秩序エリア(Rn)が得られ、R[1,2...n-1]<=R[n]が満たされる. 
3)交換後の新しい山頂R[1]は山の性質に違反する可能性があるので、現在の無秩序区(R 1,R 2,…Rn-1)を新しい山に調整し、再度R[1]と無秩序区の最後の要素を交換して、新しい無秩序区(R 1,R 2….Rn-2)と新しい秩序区(Rn-1,Rn)を得る必要がある.このプロセスは、規則化領域の要素の個数がn−1であるまで繰り返し、順序付けプロセス全体が完了する.

//   
#include
#include
using namespace std;
void AjustDown(int a[],size_t n,int parent)
{
    assert(a);
    int child = parent*2+1;
    while(childa[parent])
        {
            swap(a[child],a[parent]);
            parent = child;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int a[],size_t n)
{
    assert(a);
    for(int i=(n-2)/2;i>0;--i)
    {
        AjustDown(a,n,i);
    }
    for(int i = 0; i  
  
    ：
 
  
       ，             ，         。          ，   R[1...n]       ，   n-1 ，    R[1...n-2]          n-2 。    n-2             n-1        ，                             ，          。  n      ，            log2(n) ，               nlogn。         ，          。
 
  
3.    
 
  
 ：100W        100 
 
  
1     ；
2        100；
3         100      ；
4         100 ，       ，         ，    ；
5       ，     100    。
 
  
#pragma once
#include
#include
#include
#include
using namespace std;
const int N = 10000;
const int K = 100;
void _AjustDown(int TopK[],int size,int parent)
{
    assert(TopK);
    int child = parent*2+1;
    while( child  TopK[parent])
        {
            swap(TopK[child],TopK[parent]);
            parent = child;
        }
        else
        {
            break;
        }
    }
}
void GetTop(int a[])
{
    assert(K = 0;--i)
    {
        _AjustDown(TopK,K,0);
    }
    for(int i=0;i