두 갈래 로 된 더미

정의: 이 진 더 미 는 특수 한 더미 이 고 이 진 더 미 는 완전 이 진 트 리 또는 완전 이 진 트 리 와 비슷 합 니 다.이 진 더 미 는 쌓 인 특성 을 만족 시 킵 니 다. 부모 노드 의 키 값 은 항상 고정된 순 서 를 유지 하고 모든 노드 의 왼쪽 트 리 와 오른쪽 트 리 는 이 진 더 미 를 유지 합 니 다.
부모 노드 의 키 값 이 항상 키 노드 의 키 값 보다 크 거나 같 을 때 최대 더미 입 니 다.부모 노드 의 키 값 이 항상 하위 노드 의 키 값 보다 작 거나 같 을 때 최소 더미 입 니 다.
중점: 1. 저장 방식, 결점 과 그의 아버지 노드 아이 노드 의 위치 관 계 는 보통 배열 로 표시 합 니 다.만약 에 뿌리 노드 가 배열 에 있 는 위치 가 1 이 라면 n 번 째 위치의 서브 노드 는 각각 2n 과 2n + 1 이다.따라서 첫 번 째 위치의 하위 노드 는 2 와 3 이 고 두 번 째 위치의 하위 노드 는 4 와 5 이다.이런 식 으로 유추 하 다.1 을 기반 으로 하 는 배열 저장 방식 은 부모 노드 와 하위 노드 를 찾 는 데 편리 하 다.만약 에 저장 배열 의 아래 표 시 는 0 을 바탕 으로 한다 면 아래 표 시 된 i 노드 의 하위 노드 는 2i + 1 과 2i + 2 이다.그 아버지 노드 의 아래 표 지 는 * 8970 ° (i - 1) * 8725 ° 2 * 8971 ° 이다.
2. 노드 를 삽입 할 때 띄 우기 동작 은 배열 의 맨 끝 에 새 노드 를 삽입 합 니 다.그리고 아래 에서 전체 노드 와 부모 노드 를 올 리 고 시간 복잡 도 Olog (n);3. 노드 를 삭제 할 때 침하 작업 은 최대 더미 에 대해 루트 노드 를 삭제 하 는 것 이 최대 치 를 삭제 하 는 것 입 니 다.최소 더미 에 대해 서 는 최소 값 을 삭제 합 니 다.그리고 쌓 아 올 린 마지막 노드 를 뿌리 노드 에 채 워 넣 으 세 요.위 에서 아래로 부모 노드 와 하위 노드 를 조정 합 니 다.
4. 난서 배열 을 쌓 아 올 리 고 복잡 도 는 O (N) 이다.

#include
#include
#include
#include
#include


using namespace std;

template <class T>
class BinaryHeap
{
public:
    BinaryHeap();
    BinaryHeap(const vector &v);
    bool isEmpty() const{ return mSize == 0; }
    int size() const{ return mSize  ; }
    const T& findMin() const;

    void insert(const T& x);
    void deleteMin();
    void makeEmpty();

private:
    int mSize;
    vector array;

    void buildHeap();
    void perColateDown(int hole);

};

template<class T>
BinaryHeap::BinaryHeap() :array(12), mSize(0)
{

}

template<class T> 
BinaryHeap::BinaryHeap(const vector &v) :array(v.size() + 1), mSize(v.size())
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        array[i + 1] = v[i];
    }
    buildHeap();
}

template<class T>
const T& BinaryHeap::findMin() const
{
    if (isEmpty())
        throw string("error");

        return array[1];

}


template<class T>
void BinaryHeap::insert(const T&x)
{
    if (mSize + 1 == array.size())
    {
        array.resize(2 * mSize + 1);
    }

    //      
    int position = ++mSize;
    array[0] = x;// x    0     

    while (x < array[position / 2])
    {
        array[position] = array[position / 2];
        position /= 2;
    }
    array[position] = x;
}

template<class T>
void BinaryHeap::deleteMin()
{
    if (!isEmpty())
    {
        array[1] = array[mSize--];
        perColateDown(1);
    }
}

template<class T>
void BinaryHeap::perColateDown(int position)
{
    //           position     
    int child = 0;
    T temp = array[position];

    for (; position * 2 <= mSize; position = child)
    {
        child = position * 2;
        if (child != mSize && array[child + 1] < array[child])
        {
            child++;
        }
        if (array[child] < temp)
        {
            array[position] = array[child];
        }
        else break;
    }

    array[position] = temp;
}

template<class T>
void BinaryHeap::buildHeap()
{
    //                perColateDown ,      i       ， 
    //               。        
    for (int i = mSize / 2; i > 0; --i)
    {
        perColateDown(i);
    }
}
int main()
{

    vector<int> v = { 1, 4, 8, 9,1,1,8,7, 4, 3, 2, 4 };
    BinaryHeap<int> Bh;

    for_each(v.begin(), v.end(), [&](int a){Bh.insert(a); });

    while (!Bh.isEmpty())
    {
        cout << Bh.findMin() << endl;
        Bh.deleteMin();
    }
    system("pause");
    return 0;
}