Heaps

힙(Heap)은 특정한 구조적 및 정렬 속성을 가진 이진 트리의 일종. 힙은 주로 우선순위 큐 구현에 많이 사용됨

완전 이진 트리: 힙은 완전 이진 트리의 형태를 가져야 함. 이는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 배치되어 있어야 한다. 이 속성 덕분에 배열로 효율적으로 표현될 수 있으며, 트리의 높이를 최소화하여 접근 및 삽입, 삭제 작업의 성능을 향상시킬 수 있음.

가장 큰 element는 root가 된다. root가 max면 max heap, min이면 min heap이다.

정렬 속성 (Order Property)

최대 힙 (Max Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같은 경우입니다. 즉, 루트 노드가 가장 큰 값을 가지며, 모든 부모 노드는 자식 노드보다 큰 값을 가진다.

최소 힙 (Min Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같은 경우입니다. 즉, 루트 노드가 가장 작은 값을 가지며, 모든 부모 노드는 자식 노드보다 작은 값을 가진다.

Complete binary Tree이므로 array로 표현하기 쉽다.

Heap Specification

template <class ItemType> struct HeapType {
    void ReheapDown(int root, int bottom);
    void ReheapUp(int root, int bottom);
    ItemType *elements; // ARRAY to be allocated dynamically
    int numElements;
};

Reheap

heap조건이 깨지는 경우 다시 heap으로 만드는 것.

ReHeapDown: deleteItem 수행시에 사용됨. 삭제된 노드의 자리를 채우기 위해서 노드가 자식 노드와 비교해서 적절한 위치로 내려감.

template <class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom)
// Pre: root is the index of the node that may violate the
// heap order property
// Post: Heap order property is restored between root and bottom
{
    int maxChild;
    int rightChild;
    int leftChild;
    leftChild = root * 2 + 1;
    rightChild = root * 2 + 2;
    if (leftChild <= bottom) // Is there leftChild?
    {
        if (leftChild == bottom) // only one child
            maxChild = leftChld;
        else // two children
        {
            if (elements[leftChild] <= elements[rightChild])
                maxChild = rightChild;
            else
                maxChild = leftChild;
        }
        if (elements[root] < elements[maxChild]) {
            Swap(elements[root], elements[maxChild]);
            ReheapDown(maxChild, bottom);
        }
    }
}

ReHeapUp: InsertItem 수행시에 사용됨. 삽입된 노드가 부모노드와 비교하여 적절한 위치로 올라감.

template <class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom)
// Pre: bottom is the index of the node that may violate the heap
// order property. The order property is satisfied from root to
// next-to-last node.
// Post: Heap order property is restored between root and bottom
{
    int parent;
    if (bottom > root) // tree is not empty
    {
        parent = (bottom - 1) / 2;
        if (elements[parent] < elements[bottom]) {
            Swap(elements[parent], elements[bottom]);
            ReheapUp(root, parent);
        }
    }
}