힙(heap)

목차

개요 기본 구조 값 삽입 최대값 삭제 힙 정렬 C++ STL priority_queue

개요

힙은 이진 트리를 활용한 자료구조이며, 종류로는 최소 힙과 최대 힙이 있습니다. 최대 힙을 알면 최소 힙을 만드는 건 어렵지 않습니다. 최대 힙 자료구조는 기본적으로 아래의 세 연산을 빠르게 수행하기 위한 자료구조입니다. 최대 힙에 새로운 값을 삽입. 최대 힙 안의 최대값을 삭제. 최대 힙 안의 값 중에 최대값 찾기. 세 연산을 배열로 간단하게 처리하려고 하면, 삽입은 오1로 가능하더라도 최대값을 찾기에서 오엔이 필요함을 알 수 있습니다. 배열에서 최대값을 찾기 위해서, 배열 안의 모든 값을 조사하는 선형 검색이 필요하기 때문입니다. 반면에 힙은 이 세 개의 연산을 모두 빠르게 수행하기 위해 사용하는 자료구조로 삽입과 삭제는 로그엔 최대값 찾기는 오1로 가능합니다.

기본 구조

힙의 기본 구조는 세 가지의 규칙을 준수하는 이진 트리입니다. 규칙 1 부모 노드가 가진 원소는 항상 자식 노드가 가진 언소보다 크거나 같아야 합니다. 마지막 레벨을 제외한 레벨에서는 노드가 모두 채워져야 합니다. 마지막 레벨에서 노드는 왼쪽부터 채워져야 합니다.  이와 같이 엄격한 규칙 덕분에, 힙은 단순히 배열을 이용해도 쉽게 구현할 수 있습니다. 루트 노드의 원소 값은 H[0], 루트 노드의 자식 노드들은 H[1], H[2], .., 이런 식으로 레벨순, 그리고 레벨이 같다면 왼쪽부터 원소 값을 저장하면 간선을 따로 저장하지 않아도 되기 때문입니다.

값 삽입

힙은 값의 삽입을 오로그엔으로 해결합니다. 힙의 맵 끝에 삽입할 값을 넣습니다. 삽입한 값이 부모 노드의 값보다 크면 두 값을 서로 바꿉니다. 삽입한 값이 루트 노드에 도달하거나, 삽입한 값보다 큰 부모 노드의 값을 만날 때까지 반복합니다.

최대값 삭제

힙은 값의 삽입과 마찬가지로 최대값의 삭제도 오로그엔으로 해결할 수 있습니다. 물론 힙의 규칙은 준수되어야 합니다. 힙의 규칙을 유지하면서, 오로그엔으로 최대값의 삭제를 마치는 알고리즘은 아래와 같습니다.  부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크거나 같아야 합니다. 자식 노드가 삽입한 값보다 작거나, 자식 노드가 없을 때까지 반복하였기 때문에 성립합니다.  마지막 레벨을 제외한 레벨에서는 노드가 모두 채워져야 합니다. 처음 삭제할 때, 힙의 맨 끝에 노드를 삭제한 꼴이기 때문에 성립합니다. 마지막 레베엘에서 노드는 왼쪽부터 채워져야 합니다. 처음 삭제할 때, 힙의 맨 끝에 노드를 삭제한 꼴이기 때문에 성립합니다.

연습 문제

수 정렬하기 2. 엔개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램을 작성하세요.

#include <stdio.h> #include <algorithm> #include <vector> #include <queue> #include <iostream> using namespace std; struct max_heap { vector<int> h; void push(int v) { int idx = h.size(); h.push_back(v); while (idx != 0 && h[idx] > h[(idx - 1) / 2]) { swap(h[idx], h[(idx - 1)/2]); idx = (idx - 1) / 2; } } int top(void) { return h[0]; } void pop(void) { h[0] = h.back(); h.pop_back(); int idx = 0; while (true) { int child = 2 * idx + 1; if (child >= h.size()) break; if (child + 1 < h.size() && h[child + 1] > h[child]) { child++; } if (h[idx] >= h[child]) break; swap(h[idx], h[child]); idx = child; } } }mh; int main() { int n; scanf("%d", &n); //cin >> n; for (int i = 0; i < n; i++) { int v; // cin >> v; scanf("%d", &v); mh.push(-v); } for (int i = 0; i < n; i++) { printf("%d\n", -mh.top()); // cout << -mh.top() << endl; mh.pop(); } return 0; }

이진 트리. 힙. 배열을 사용해서 구현 하였습니다. 최대힙이라는 구조체를 만들었는데. 여기서 제일 위에. 그리고 넣는 것과 빼는 것을 나타냈습니다. 넣을때는 먼저 가장 마지막 단에 넣은 다음에, 루트나, 바로 위의 한단계 부모의 숫자가 자기 자신 보다 클때까지 와일문을 돌리는 것이 핵심이니다. 여기서 필요한 변수는 현재의 인덱스를 가지고 있는 idx 입니다. 그리고 제일 최대값을 빼는 함수는 단순하게 루트 h[0] 의 숫자를 빼내면 됩니다. 그리고 다음으로 제일 최대값을 출력해주었으므로. 최대값을 제거하려면 제일 아래 있던 숫자를 제일 위의 루트 숫자에 넣은 다음에 자식 인데스에 속해 있는 값들과 비교하면서 하나씩 내려오도록 구현 하면 됩니다. 그래서 필요한 변수는 idx  와 child 입니다. child 중에서도 큰 수와 비교하기 위해서 한번 child 변수를 ++ 해주는 부분이 필요합니다. (조건문)