[알고리즘/자료구조] Heap/Heap sorting
해당 게시글은 비전공자이자 초보 개발자 지망생이 작성한 글로 정확하지 않을 수 있으니 참고해주시길 바랍니다!
피드백과 정보 정정 댓글은 환영입니다 :)
퀵정렬까지 한꺼번에 정리하려고 했으나 생각해보니 저번 학기 자료구조 강의를 들으며 힙에 대해 배웠던 터라... ㅎ
더 기억이 사라지기 전에 한꺼번에 정리해보려 한다!
1) Heap이란?
Heap은 아래의 특성을 가진 이진 트리 (Binary Tree)의 구조를 따른다.
- 트리는 완전하거나 거의 완전해야 한다. (Complete or Nearly Complete)
- 각 노드의 key value는 자신의 후손들보다 항상 크거나 같아야 한다. (max-heap) 따라서, Heap (앞으로 언급하는 heap은 특별한 언급이 없는 이상 모두 max-heap을 가리킨다.) 의 root 에는 전체 원소들 중 가장 큰 값이 자리한다.
* min-heap의 경우 key value가 자신의 후손들보다 항상 작거나 같아야 한다.
이러한 특성은 한 노드의 양쪽 트리에도 똑같이 적용되기에 힙은 Self recursive으로 정의된 자료구조이다. Heap은 linked list 보다 주로 array로 구현된다. 뒤에서 다룰 예정이긴 하나 간단하게 설명하면 heap의 원소들은 Index로 찾기 때문에 index로 바로 접근할 수 있는 array가 값을 찾기에는 더 유용하다.
Heap의 Property는 노드를 Insert하고 Delete할 때 바뀔 염려가 있다. 따라서, 해당 operations 들을 수행하기 위해서는 Heap의 property를 유지시키기 위한 reheap up과 reheap down 알고리즘이 필요하다.
2) Reheap Up
Reheap Up은 노드의 삽입이 이루어질 때 작동한다. 노드의 삽입은 힙의 가장 마지막 부분에서 이루어지는데, 이후 이 삽입된 원소를 자신의 부모 노드와 비교하며 연산을 수행한다. 부모 노드보다 자식이 작으면 작동을 중지, 부모 노드보다 자식이 크면 자리를 바꾼 후 다시 바뀐 자리의 부모 노드와 값을 비교한다. 이 연산은 노드가 적절한 자리를 찾을 때까지 지속적으로 수행한다. 다음 사진들은 57이 새로 삽입되었을 때 reheap up을 통해 Max-heap property를 회복하는 과정을 나타낸 것이다.
3) Reheap Down
Reheap Down은 노드의 삭제가 이루어질 때 작동한다. Heap에서 원소의 삭제는 가장 첫 노드에서 이루어진다. 첫 노드의 삭제가 이루어지면 첫 원소를 힙의 가장 마지막 원소로 대체한다. 이후 root와 자식들을 비교하는데, 자식들(left, right) 중 값이 더 큰 원소를 root와 교환한다. 이 연산은 노드가 적절한 자리를 찾을 때까지 지속적으로 수행한다.
4) Heap Implementation
Heap은 앞서 잠깐 언급한 것처럼 Index를 통한 접근을 위해 Array로 구현된다. 부모와 자식 노드의 관계 또한 인덱스로 설명이 가능하다. 부모 노드의 index를 i라고 뒀을 때 Left child의 인덱스는 2i + 1, Right child의 인덱스는 2i + 2 로 표현할 수 있다. (힙의 가장 첫 원소의 인덱스가 0이라고 가정하였을 때입니다.) 반대로 child의 부모 노드는 (i-1)/2를 내림수 (버림수)한 것이고, complete 의 size가 n일 때 첫 leaf (자식이 없는 노드) 노드의 인덱스는 (n/2)를 내림수 (버림수) 한 것이다.
5) ADT로 heap 구현
다음은 추상 자료형 (Abstract Data Type)으로 힙 알고리즘을 구현한 것이다. 완전한 이해는 아니지만 내가 이해한 것으로 추상 자료형을 설명하자면 ... 힙을 예시로 들었을 때, 힙에 담긴 내용물이 무엇일지 모르기에 (str, pointer, int and etc) 모든 자료형을 담을 수 있는 Heap을 구현한 것이라고 이해하였다. 해당 자료구조는 C언어로 구현하였다.
static void _reheapUp( HEAP *heap, int index){
void* temp ;
if (heap->last != 0){
if ((heap->compare)(heap->heapArr[index], heap->heapArr[(int) (index - 1)/2])>0){
temp = heap->heapArr[(int) (index - 1)/2];
heap->heapArr[(int) (index - 1)/2] = heap->heapArr[index];
heap->heapArr[index] = temp;
_reheapUp(heap, (int) (index - 1)/2) ;
}
}
}
static void _reheapDown( HEAP *heap, int index){
void *leftkey;
void *rightkey;
void *temp;
int l_index;
if (2*index+1<=heap->last){
leftkey = heap->heapArr[2*index+1];
if(2*index+2<=heap->last) rightkey = heap->heapArr[2*index+2];
else rightkey = NULL;
if (rightkey==NULL) l_index = 2*index+1;
else if (leftkey==NULL) l_index = 2*index+2;
else {
if ( (heap->compare)(leftkey, rightkey)>0) l_index = 2*index+1;
else l_index = 2*index+2;
}
if ( (heap->compare)( heap->heapArr[index], heap->heapArr[l_index])<0){
temp = heap->heapArr[l_index];
heap->heapArr[l_index] = heap->heapArr[index];
heap->heapArr[index] = temp;
_reheapDown(heap, l_index);
}
}
}
6) 힙의 활용, Heapsort
Max Heap property를 활용하여 array를 정렬할 수 있다. 다음은 힙정렬을 파이썬 코드로 구현한 것이다.
import math
#In this code, Heap's index starts from 0
def MaxHeapify(A, i, heap_size):
l = 2*i + 1 #left child
r = 2*i #right child
if l < heap_size and A[l] > A[i]:
largest_index = l
else:
largest_index = i
if r < heap_size and A[r] > A[largest_index]:
largest_index = r
if largest_index != i:
#exchanging larger child node with parent node
tmp = A[largest_index]
A[largest_index] = A[i]
A[i] = tmp
MaxHeapify (A, largest_index, heap_size)
def BuildMaxHeap(A, heap_size):
for i in range(int((heap_size-1)/2), -1, -1):
MaxHeapify (A, i, heap_size)
def HeapSort(A):
heap_size = len(A)
BuildMaxHeap(A, heap_size)
for i in range(heap_size-1, 0, -1):
#exchanging first one and last one, to loace the largest element in back
tmp = A[i]
A[i] = A[0]
A[0] = tmp
heap_size = heap_size - 1
MaxHeapify (A, 0, heap_size)
return A