Heap / 힙
힙은 완전이진트리(complete binary tree) 기반 자료구조이며,최댓값혹은최솟값을 빠르게 찾을수 있는 자료구조이다.- 부모 자식간의 관계만 중요하며 형제 노드들과는 관계가 없다.
max heap: 루트 노드가 모든 자식에 존재하는 키 중에서 가장 크다, 이 속성은 하위 노드의 서브트리에서도 반복적으로 적용된다.min heap: 루트 노드가 모든 자식에 존재하는 키 중에서 가장 작다, 이 속성은 하위 노드의 ㄹ서브트리에서도 반복적으로 적용된다.- 힙을 배우기 위해선
arraytree두가지 자료구조를 알야아 한다.
Properties / 속성
- 완벽한 이진트리는 어떤 노드든 특정 노드의 부모 노드와 자식 노드를 찾을수 있는 속성을 가지고있다.
- 만약 배열에서의 특정 요소가
i라면, 왼쪽자식 노드의 인덱스는2i+1이 될것이고, 오른자식 노드의 인덱스는2i+2가 된다. 또한 부모노드의 경우(i-1)//2가 된다.
- 위 그림은 배열에서의 인덱스가 이진트리와의 관계를 나타낸다. (맥스힙도 같음).
| index | Eng | Kor |
|---|---|---|
| Arr[(i-1)/2] | Returns the parent node | 부모노드 |
| Arr[(2*i)+1] | Returns the left child node | 왼쪽 자식 노드 |
| Arr[(2*i)+2] | Returns the right child node | 오른쪽 자식 노드 |
Max Heap
- 각 노드의 값은 부모노드보다 작거나 같다 / 부모노드가 항상 크거나 같다 / 루트가 제일 크다.
- 내림차순에 사용된다.
pop이 호출되면 루트가(가장 큰 값) 우선으로 사라진다.
Implementation
Push
- 트리의 가장 마지막 노드의 다음 자리에 현재 삽입하고자 하는 데이터를 넣어준다.
- 부모노드와 비교하면서 부모 노드보다 더 큰 값이라면 부모노드와 Swap.
- 위 조건을 만족하지 않을때까지 반복.
Pop
최댓값을 미리 저장후 마지막 노드와 루트 노드를swap.- 바꾼 후 루트 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.
- 더이상 작은값이 나오지 않을때까지 위 과정을 반복한다.
- 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.
// standard input and output
#include <stdio.h>
// srand
#include <stdlib.h>
// time
#include <time.h>
// 2^8
#define HEAP_SIZE 256
#define ARRAY_SIZE 10
using namespace std;
int heap[HEAP_SIZE];
// heap count is representing that the number of indices and the end index number of a heap DS.
int heap_count = 0;
void swap(int * a, int * b) {
int temp = *a;
*a = *b;
*b = temp;
}
void push(int data) {
heap[++heap_count] = data;
int child = heap_count;
int parent = child / 2;
while (child > 1 && heap[parent] < heap[child]) {
swap(&heap[parent], &heap[child]);
child = parent;
parent = child / 2;
}
}
int pop() {
// returning the first element of a heap DS.
int result = heap[1];
swap(&heap[1], &heap[heap_count]);
heap_count--;
// Reconstructing tree structure after popping a root node.
int parent = 1;
int child = parent * 2;
if (child + 1 <= heap_count) {
child = (heap[child] > heap[child + 1]) ? child : child + 1;
}
while (child <= heap_count && heap[parent] < heap[child]) {
swap(&heap[parent], &heap[child]);
parent = child;
child = child * 2;
if (child + 1 <= heap_count) {
child = (heap[child] > heap[child + 1]) ? child : child + 1;
}
}
return result;
}
int main() {
int arr[ARRAY_SIZE];
srand(time(NULL));
// Generating random number from 1 to 50.
for (int i = 0; i < ARRAY_SIZE; i++) arr[i] = rand() % 50 + 1;
printf("Pushing random numbers repeatedly into a max heap: \n");
for (int i=0; i<ARRAY_SIZE; i++) push(arr[i]);
for (int i=0; i<ARRAY_SIZE; i++) printf("%d ", arr[i]);
printf("\n\n");
// Descending order
printf("Popping max heap: \n");
for (int i=0; i<ARRAY_SIZE; i++) printf("%d ", pop());
printf("\n");
return 0;
}
Min Heap
- 각 노드의 값은 부모노드보다 크거나 같다. / 부모노드가 항상 작거나 같다 / 루트가 제일 작다.
- 오름차순에 사용된다.
pop이 호출되면 루트가(가장 작은 값) 우선으로 사라진다.
Implementation
Push
- 트리의 가장 마지막 노드의 다음 자리에 현재 삽입하고자 하는 데이터를 넣어준다.
- 부모노드와 비교하면서 부모 노드보다 더 작은 값이라면 부모노드와 Swap.
- 위 조건을 만족하지 않을때까지 반복.
Pop
최솟값을 미리 저장후 마지막 노드와 루트 노드를swap.- 바꾼 후 루트 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.
- 더이상 작은값이 나오지 않을때까지 위 과정을 반복한다.
- 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
// 2^8
#define HEAP_SIZE 256
#define ARRAY_SIZE 10
int heap[HEAP_SIZE];
// heap count is representing that the number of indices and the end index number of a heap DS.
int heap_count = 0;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void push(int data) {
heap[++heap_count] = data;
int child = heap_count;
int parent = child/2;
while(1<child && heap[parent]>heap[child]) {
swap(&heap[parent], &heap[child]);
child = parent;
parent = child/2;
}
}
int pop() {
int result = heap[1];
swap(&heap[1], &heap[heap_count]);
heap_count--;
int parent = 1;
int child = parent*2;
if(child+1<=heap_count) {
child = (heap[child]<heap[child+1]) ? child : child+1 ;
}
while(child<=heap_count && heap[parent]>heap[child]) {
swap(&heap[parent], &heap[child]);
parent = child;
child = child*2;
if(child+1<=heap_count) {
child = (heap[child]<heap[child+1]) ? child : child+1 ;
}
}
return result;
}
int main() {
int arr[ARRAY_SIZE];
srand(time(NULL));
//Generating random numbers from 1 to 50.
for(int i=0; i<ARRAY_SIZE; i++) arr[i] = rand()%50 + 1;
printf("Pushing random numbers repeatedly into a heap DS.\n");
for(int i=0; i<ARRAY_SIZE; i++) push(arr[i]);
for(int i=0; i<ARRAY_SIZE; i++) printf("%d ", arr[i]);
printf("\n\n");
// Ascending order;
printf("Popping min heap: \n");
for(int i=0;i<ARRAY_SIZE; i++) printf("%d ", pop());
printf("\n");
return 0;
}
References
권오남 / Onam Kwon