[lecture] Heap

heap은 binary tree의 일종이다. 

HEAP

1. 최대 힙 >> 부모 노드는 자식 노드보다 작지만 않으면 된다. + 완전이진트리이다.

• 최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다.
• 최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.

2. 최소 힙 >> 부모 노드는 자식 노드보다 크지만 않으면 된다. + 완전이진트리이다.

• 최소 트리(Min Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 크지 않은(=작거나 같은) 트리이다.
• 최소 힙(Min Heap)은 최소 트리(Min Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.

부모자식간의 관계를 의미하고, 자식간에는 관계 없다.

heap를 나타내는 방법에는 1. 배열 2. 연결리스트 이 있다.

배열에 대한 장점 : 힙은 완전 이진 트리이기 때문에 부모-자식을 표시하기에 가장 쉽다.

//heap structure
#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS - 1)	//같으면 full
#define HEAP_EMPTY(n) (!n)	//n=0와 같은 말
typedef struct{
	int key;
    /* other field */
} element;
element heap[MEX_ELEMENTS];
int n = 0; 	//n은 배열의 개수

priority queue

나갈 때 가장 우선 순위가 낮거나 높은 얘가 나감 >> max/min에 따라 root가 나감 ( 일반 FIFO queue와 다름)

representation	insertion	deletion
unordered array	O(1)	O(n)
unordered linked list	O(1)	O(n)
sorted array	O(n)	O(1)
sorted linked list	O(n)	O(1)
max heap	O(log2n)	O(log2n)

time complexity 관점에서 작성된 표이며, space complexity는 전부 O(n)이다.

삽입되는 원소의 정확한 위치를 결정하기 위해, 트리의 새 노드에서 시작해서 루트쪽으로 올라가는 방법을 사용한다. 삽입되는 원소는 새 노드에 삽입이 되고나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다. 부모 노드보다 값이 클 경우, 서로 교환하면서 위로 올라가는 과정을 반복하는 것이다.

새로 삽입되는 노드는 bottommost-rightmost leaf node 에서 생성되고, from learf to root로 이동시킨 후 new key value 값을 삽입. parent position 은 i/2. >> 시간복잡도는 O(log₂n). depth of tree가 n

//insertion into a max heap
void insert_max_heap(element item, int *n){
	int i;
    if(HEAP_FULL(*n)){
    	fprintf(stderr, "The heap is full.\n");
        exit(1);
    }
    i = ++(*n);
    while((i != 1) && (item.key > heap[i/2].key)){
    	heap[i] = heap[i/2];	//그 값을 child로 내림
        i /= 2;
    }
    heap[i] = item;
}
//deletion into a max heap
element delete_max_heap(int *n){
	element item, temp;
    if(HEAP_EMPTY(*n)){
    	fprintf(stderr,"The heap is empty\n");
        exit(1);
    }
    item = heap[1];	//root
    temp = heap[(*n)--];	//right most leaf, 원소 개수 하나 줄어듦
    parent = 1; child = 2;
    while(child <= *n){
    	/* compare left and right child's key values */
        if((child < *n) && (heap[child].key < heap[child + 1].key))
        	child++;
        if(temp.key >= heap[child].key) break;
        /* move to the next lower level */
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

sorting heap sort > O(nlog₂n)
selection sort > O(n²)
Quick sort, Merge sort > O(nlog₂n)