Heap

What is a Heap?

local variable은 stack에 있고, dynamic 은 heap에 있다의 heap과 다르다. 맥락을 통해 구분하자.

 

Heap은 binary tree의 한 종류이다. 다음의 두 가지 특징을 만족해야한다.

1. Shape : It must be a complete binary tree

2. Order :  모든 노드는 자기의 children 값보다 커야 한다. (Parent가 가장 커야함) _ Max_Heap

                  모든 노드를 자기의 children 값보다 작게 하는 Min_Heap도 만들 수 있다.

 

 

Example of heap

전체 트리에서 가장 큰 Element = root 

Heap

 

ReheapDown(int root, int bottom)

• 가장 큰 노드를 root로 올리고 작은 노드를 down 하려는 목적
• order가 안 맞는 상황에서 사용. delete를 하다보면 이런 상황이 자주 생긴다. -> 다시 힙으로 만들자. 

1. 자식들 중 큰 노드랑 swap

2. swap으로 생긴 트리 heap인지 확인. order 안 맞으면 다시 자식들 중 큰 노드와 swap.

 

I > H > E

template <class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom){
	int maxChild, leftChild, rightChild;
    leftChild = root*2 + 1;
    rightChild = root*2 + 2;
    
    //maxChild 찾기
    if(leftChild <= bottom){                                    //값 비교가 아니라 index 비교
    	if(leftChild == bottom)                                 //only one child
        	maxChild = leftChild;
        else{                                                   // two child
        	if(elements[leftChild] <= elements[rightChild])     //값 크기 비교
            	maxChild = rightChild;
            else
            	maxChild = leftChild;
            }
        }
      
    //root와 비교하고 실질적인 작업 수행
    if(elements[root] < elements[maxChild]){
    	Swap(elements[root],elements[maxChild]);
        ReheapDown(maxChild,bottom);
        }

 

ReheapUp(int root, int bottom)

다 괜찮은데 마지막 노드 때문에  heap이 안되는 경우에서 사용. insert 할 때 많이 쓴다.

1. 부모 노드와 swap.

2. swap 이후 heap이 될 때까지 부모 노드와 값 비교하며 swap.

K > G

 

template <class ItemType>
void HeapType<ItemType>::ReHeapUp(int root, int bottom){
	int parent;
    
    if(root > bottom){                   //Tree is not empty
   		parent = (bottom-1)/2;
        if(elements[parent] < elements[bottom]){
        	Swap(elements[parent],elements[bottom]);
            ReHeapUp(root,parent);
        }}}

 

DeleteItem

(1) 힙의 가장 마지막 요소(right most element)를 삭제하려는 요소 위치에 덮어쓴다.

(2) right most node를 삭제한다.

(3) ReheapDown을 이용해 다시 힙 구조를 맞춰준다.

 

InsertItem

(1) 추가하려는 요소를 힙의 가장 마지막 위치( leftmost place)에 넣는다.

(2) ReheapUp을 이용해 다시 힙 구조를 맞춰준다.