[자료구조] - Heap

 

 

heap (Data Structure) 이 되려면?

• Complete binary tree가 되어야 한다.
• (tree가 비어있다면 오른쪽 젤 아래만이 비어있어야 한다. 노드 중간에 비어 있으면 안 된다.

 

• heap-order property를 만족해야 한다.
• 부모는 자식보다 값이 무조건 크거나 같아야 한다.

​

heap

• heap은 array로 구성한다. (구현한다)
  → length : array의 크기 heap-size : 실제로 힙으로 사용되는 노드의 개수 (array 내에서)

 

• root 노드는 A[0], 그 밑 노드는 A[1], 그 밑 노드는 A[2] …

​

• Parrent(i) → return (i)/2
• LeftChild(i) → return 2*(i)
• RightChild(i) → return 2*(i) + 1
  → binary tree라 식이 성립한다.

​

• heap property를 만족하는가? → A[Parent(i)] ≥ A[i]
• height(높이) : 트리에서 가장 긴 edge의 개수가 높이가 된다.
• 시간 복잡도 : log2 n (n=노드 개수)

 

• 어떤 array가 준비가 되면 heap으로 바꿔주는 일을 “Heapify”라고 한다.

​

​

 

---

 

 

 

Other heap Operations

 

• Heap Insert
• Heap Extract
• Heap Delete
• Heap Sort → 시간 복잡도 ( N log2 N)

​

• <algorithm> : 표준 힙 구현에 필요한 헤더 파일
• <vector> : vector 생성 (?)

 

• make_heap ( v.begin(), v.end() ); - 힙 만들기
• pop_heap( v.begin(), v.end() ); - 루트 노드와 리프 노드를 서로 교환한다.
• v.pop_back(); - 맨 마지막 값을 뺀다. pop_heap을 하고 나면 pop_back을 해줘야 한다. heap에서 1개를 뺏기 때문에 length와 heap_size 의 값을 맞춰줘야 하기 때문이다.
• v.push_back(?); - 노드 제일 마지막에 ? 값을 추가한다.
• push_heap( v.begin(), v.end() ); - push_back 한 뒤에 push_heap을 해줘야 다시 힙이 만들어진다. (가장 최근에 들어온 값을 먼저 heapify 시킨다.) → make_heap이랑은 다른 개념