힙(Heap) 자료구조란?

Heap

- 최대값 또는 최소값을 빠르게 구하기 위한 자료구조

- 완전 이진 트리를 기본으로 한 자료구조

- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.

- 트리가 한쪽으로 기울어진 편향적인 상태를 방지하여 트리의 높이를 항상 일정.

- 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상.

  부모 자식간의 관계만 중요하기 때문에 왼쪽 자식과 오른쪽 자식에 대해서는 크기 제한 X

- 최대값 or 최솟값이 Root에 위치하기에 해당 값을 찾을 시 연산이 효율적.

    - 최대 힙(Max Heap): 부모노드 값 ≥ 자식 노드 값

    - 최소 힙(Min Heap): 부모노드 값 ≤ 자식 노드 값

　

완선된 Heap은 아래와 같습니다. 

- Max Heap이므로 Root Node에 위치한 값은 최대값입니다.

- 부모 노드 ≥ 자식 노드 관계 입니다.

 

※ [그래프] 힙(Heap) 시뮬레이션 

힙(Heap) 시뮬레이션

 

Heap 구조 활용

- 우선순위 큐 (Priority Queue)  

우선순위 큐 (Priority Queue)

- 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

- [예제] 힙 정렬 

[예제] 힙 정렬 구현

구현

#include <stdio.h>

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

void heapify(int array[], int n, int i) {
    int parentNode = i;
    int leftChildNode = i * 2 + 1;
    int rightChildNode = i * 2 + 2;


    // 왼쪽 자식 노드가 존재하면서 부모노드와 값 비교.
    if (leftChildNode < n && array[parentNode] < array[leftChildNode]) {
        parentNode = leftChildNode;
    }
    // 오른쪽 자식 노드가 존재하면서 부모노드와 값 비교.
    if (rightChildNode < n && array[parentNode] < array[rightChildNode]) {
        parentNode = rightChildNode;
    }


    // 왼쪽 or 오른쪽 자식 노드 중 부모 노드보다 큰 값이 존재한 경우
    if (i != parentNode) {
        swap(&array[parentNode], &array[i]);
        // 초기 부모노드가 제자지를 찾을 때까지 내려갑니다.
        heapify(array, n, parentNode);
    }
}

void main(void) {
    int n = 9;
    int array[9] = { 7, 6, 5, 8, 3, 5, 9, 1, 6 };


    // 최대 힙(Max Heap) 구성
    for (int i = (n / 2) - 1; i >= 0; i--) {
        heapify(array, n, i);
    }


    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
}

 

관련 문제

- [BOJ] 1927 최소 힙

- [BOJ] 11279 최대 힙

- [BOJ] 17612 쇼핑몰

- [BOJ] 2696 중앙값 구하기

- [BOJ] 1655 가운데를 말해요

- [Jungol] 2082 힙정렬2 (Heap_Sort)

- [Jungol] 1190 모두 더하기

- [Jungol] 1318 못생긴 수

- [Jungol] 1929 책꽂이 만들기

- [Jungol] 1570 중앙값

- [Algospot] RUNNINGMEDIAN 변화하는 중간값