5-5강 - Heap (힙)

6. Heap

0) Priority Queue

우선 순위가 가장 높은(혹은 낮은) 원소를 먼저 삭제한다.

1> linear list으로 구현

- isEmpty : O(1)

- top : O(n)

- push : O(1)

- pop : O(n)

2> max heap으로 구현

- isEmpty : O(1)

- top : O(1)

- push : O(logn)

- pop : O(logn)

 

1) Heap의 정의

1> max heap

(자식 node가 존재할 때) 각 node의 key value이 그 자식의 key value보다 작지 않은 tree

max heap은 complete binary tree이면서 max tree이다.

2> basic operation

- Creation of an empty heap
- Insertion of a new element into the heap
- Deletion of the largest element from the heap

 

2) The Heap Abstract Data Type

(max heap 기준)

1> Object

: node가 0개 이상인 complete binary tree이며 각 node는 children보다 크다.

2> Fuction

- MaxHeap Create(max_size) ::= create an empty heap that can hold a maximum of max_size elements.
- Boolean HeapFull(heap,n) ::= if (n==max_size) return TRUE
                                         else return FALSE
- MaxHeap Insert(heap,item,n) ::= if(!HeapFull(heap,n)) insert an item into heap and return the resulting heap                                                        else return error.
- Boolean HeapEmpty(heap,n) ::= if(n<=0) return TRUE
                                            else return FALSE
- MaxHeap Delete(heap,n) ::= if(!HeapEmpty(heap,n)) return one of the largest element in the heap and remove it from the heap                    else return error.

 

3) Insertion Into A Max Heap

 

4) Delete From A Max Heap