Heap

Task Set
- Heap에 대해 알아본다.
- Max Heap의 구현 방법을 살펴본다.

---

Heap 이란?

Heap은 우선순위 큐(Priority Queue)를 위해 만들어진 자료구조이다.

우선순위 큐란, 큐의 성질에 더해 가변적인 데이터들에 대해 오름차순 또는 내림차순으로 정렬이 되어있는 자료구조이다.

 

Heap의 특징으로는 다음과 같다.

• 거의 완전 이진 트리이다. (nearly complete binary tree)
• 중복된 값을 허용한다.
• 삽입, 삭제가 O(log n)의 시간복잡도를 갖는다.

# 거의 완전 이진 트리인 이유는 연속되어야 배열로써 표현이 가능하고, 자식의 개수를 유추할 뿐만아니라 부모 - 자식간의 연결 관계를 수식화 할 수 있기 때문이다.

 

Heap의 종류로 Max Heap, Min Heap 2가지가 있다.

Max Heap은 부모 노드가 자식 노드보다 크거나 같은 상태에 있다.

Min Heap은 부모 노드가 자식 노드보다 작거나 같은 상태에 있다.

위와 같은 상태를 반정렬 상태라고 한다.

 

Max Heap, Min Heap의 구현

Max Heap과 Min Heap의 구현 차이는 비교 연산을 반대로 하는 것 밖에 없다. 따라서 둘 중 하나만 구현하면 나머지 하나는 조금만 생각해도 구현이 가능하다.

 

Max Heap을 살펴보자.

먼저 배열에서의 부모와 자식 관계는 다음과 같이 나타낼 수 있다.

Parent(i)
	return floor(i/2)

Left(i)
	return 2i

Right(i)
	return 2i + 1

 

다음은 Max Heap의 예시이다.

위 그림과 같이 배열로 표현하면 삽입, 추출 연산이 간편해진다.

 

삽입의 과정

1. Heap의 크기를 하나 늘리고, 배열의 맨 뒤에 값을 삽입한다.
2. 재귀적으로 부모와 비교하여 자신의 자리를 찾아간다.

추출의 과정

1. 트리의 루트 노드의 값을 임시 저장한다.
2. 배열의 맨 뒤의 값을 첫 번째 인덱스의 위치로 옮긴 후, Heap의 크기를 하나 줄인다.
3. 재귀적으로 자신의 자리를 찾아간다.

 

이를 코드로 표현하면 다음과 같다.

#include <iostream>
using namespace std;
#define MAX 100001

/*
2023. 9. 15.
Data Structure - Max Heap
*/

struct Heap {
    int data[MAX];
    int size = 0;
};

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void insertHeap(Heap *h, int x) {
    h->data[++h->size] = x;

    for (int i = h->size; i / 2 >= 1; i /= 2) {
        if (h->data[i] <= h->data[i / 2]) break;
        else swap(h->data[i], h->data[i / 2]);
    }
}

int popHeap(Heap *h) {
    int ret = h->data[1];
    h->data[1] = h->data[h->size--];

    for (int child, i = 1; i * 2 <= h->size; i = child) {
        child = i * 2;
        if (child + 1 <= h->size && h->data[child] <= h->data[child + 1]) ++child;

        if (h->data[i] < h->data[child]) swap(h->data[i], h->data[child]);
        else break;
    }

    return ret;
}

 

MinHeap은 대소 비교를 반대로 바꿔주면 완성된다.