자료구조[9] Heap

‍박성령·2024년 11월 30일

자료구조

목록 보기

9/12

Heap

개요

heap은 특정한 shape와 order를 만족시키는 binary tree이다.

SHAPE: complete binary tree 조건 1
ORDER: parents value > Child values 조건 2

이러한 order 특성으로 tree의 최댓값은 root에 저장되어있으므로 O(1)로 최댓값을 찾을 수 있다.

Heap은 operation 관점에서 array로 구현하는 것이 좋기 때문에 array로 구현하도록 한다.
array로 구현하면 부모 자식 노드의 index를 알 수 있기 때문에 쉽게 접근이 가능하기 때문이다.
이러한 Heap은 priority queue, heap sort등에서 활용한다.

Heap Operation

insertItem()

Logical Level

heap의 특성을 유지하면서 어떻게 Insert를 할 수 있을까?

Shape 특성을 유지하기 위해 맨 왼쪽 아래에 넣는다.

Order 특성을 유지하기 위해 ReheapUp이라는 과정을 거친다.

위의 heap에 65란 item을 insert 한다고 해보자.

먼저 맨 아래 왼쪽에 65를 넣어준다.

그 후 부모 노드보다 값이 크다면 위치를 바꿔준다.

다시 바꿔준다.

root 노드보단 크지 않으므로 이대로 마무리한다.

이러한 과정을 ReheapUp이라 한다.

Implementation Level

reheapUp을 구현해보자.

template<class ItemType>
void HeapType<ItemType>::reheapUp(int root, int bottom_id){
	int parent;
    
    if (bottom_id > root){
    	parent = (bottom_id - 1) / 2;
        if (items[parent] < items[bottom_id]){
        	swap(items[parent], items[bottom_id]);
            reheapUp(root, parent);
        }
    }
}