힙 (Heap)

힙(heap) 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다.

힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.
또한 자식노드 사이의 상관관계는 없으므로 유의하여야 합니다.
부모 노드의 값이 자식 노드의 값보다 크다면 최대 힙(Max Heap), 부모 노드의 값이 자식 노드의 값보다 작다면 최소 힙(Min Heap) 으로 부릅니다.
힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에, O(1) 만에 최댓값과 최솟값을 찾을 수 있습니다.

최소 힙의 예시

힙의 삽입은 트리의 가장 마지막 부분에 데이터를 삽입한 후, 부모 노드와 삽입 부분 노드의 대소 관계를 확인하여 힙의 규칙에 맞도록 부모 노드를 탐색, 스왑하는 과정으로 이루어져 있습니다.

트리의 마지막에 추가

부모 노드와 비교하여 스왑

힙의 조건을 만족함

힙의 삭제는 삭제할 원소를 삭제 한 후 트리의 가장 마지막 원소를 삭제된 원소의 위치에 넣어준 후 힙의 조건을 만족하는 적절한 위치에 이를 수 있도록 조정해주면 됩니다.

제일 마지막 원소를 삭제된 원소 자리로 옮긴다.

힙의 규칙에 맞게 부모와 자식의 자리를 바꿔준다.

삭제가 완료된 힙 구조

힙의 삽입과 삭제의 시간 복잡도는 최악의 경우 최하단 노드로부터 최상단 노드까지 스왑이 필요하게 됩니다. 따라서 O(log N)의 시간 복잡도를 가집니다.
완전이진트리를 사용하기 때문에 최대 사이즈의 배열로 선언 후 쉽게 구현할 수 있습니다.

다음은 C++로 나타낸 코드입니다.

#include <iostream>
#include <algorithm>

#define MAX 5005

using namespace std;

int heap[MAX];

int main()
{
	int n;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int m;

		cin >> m;

		heap[i] = m;

		for (int j = i; j > 1; j /= 2) {
			if (heap[j] > heap[j / 2]) {
				swap(heap[j], heap[j / 2]);
			}
		}

	}

	for (int i = 1; i <= n; i++) {

		swap(heap[1], heap[n - i + 1]);

		for (int j = 1; ; ) {

			int k = j * 2;

			if (k > n - i) break;

			if (k + 1 <= n - i && heap[k] < heap[k + 1]) k++;

			if (heap[j] < heap[k]) {
				swap(heap[j], heap[k]);
				j = k;
			}

			else break;
		}

	}

	for (int i = 1; i <= n; i++)

		cout << heap[i] << " ";

	return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        ArrayList<Integer> heap = new ArrayList<>();
        ArrayList<Integer> ans = new ArrayList<>();

        heap.add(0); // for 1-based tree

        for (int i = 1; i <= n; i++) {
            heap.add(scanner.nextInt());
            for (int j = i; j > 1; j /= 2) {
                if (heap.get(j) < heap.get(j / 2)) {
                    int temp = heap.get(j);
                    heap.set(j, heap.get(j / 2));
                    heap.set(j / 2, temp);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            ans.add(heap.get(1));
            heap.set(1, heap.get(n - i + 1));
            for (int j = 1; ; ) {
                int k = j * 2;
                if (k > n - i) break;
                if (k + 1 <= n - i && heap.get(k) > heap.get(k + 1)) k++;
                if (heap.get(j) > heap.get(k)) {
                    int temp = heap.get(j);
                    heap.set(j, heap.get(k));
                    heap.set(k, temp);
                    j = k;
                }
                else break;
            }
        }

        for (int i = 0; i < n; i++)
            System.out.print(ans.get(i) + " ");
    }
}

다음 시간엔 해쉬에 대해 알아보겠습니다.