자료구조 Heap / Heap_Sort

== Heap ==

- Heap Tree 

- Root 값에 따라서 max heap과 min heap으로 나뉜다.

- A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: Min-heap, Max-heap.

- heap의 특성은 탁 1개이다. parent node가 child node 보다 크면 heap 이다! 

- Heapify, 일반적인 tree를 heap-tree로 바꾸는 것을 말한다!! 

def heapify(a, size): p = (size//2) -1 # 자식노드가 있는 노드부터 보기 위해서!! while p>=0: siftdown(a,p,size) p -= 1

- Siftdown, 자식노드 중에 큰값이 있는지 확인하는 계속 들어간다!! 

def siftdown(a, i, size): l = 2*i+1 # left child node r = 2*i+2 # right child node largest = i if l <= size-1 and a[l] > a[i]: largest = l if r <= size-1 and a[r] > a[largest]: largest = r if largest != i: swap(a, i, largest) siftdown(a, largest, size)

- Heap은 언제 쓰이나?!

- 가장 비싼 노트북의 여분을 보고 싶을 때!! heap이면 단 한번의 index, root값만 알려주면 된다!! 매우 빠르다!! 

== Heap Sort ==

- Time Complexity

- Run time : worst-case O(n log n)

- O(1) for get root value (max, min value)

- Space Complexity : Heap_sort is an in-place algorithm(또 다른 메모리를 필요로 하지 X)

- Max-heap을 정렬하는 것 봄!! 

source code : The-G

---

reference : 상상개발자