Heap
Heap
- A heap is a specialized tree-based data structure that satisfies the heap property: it is a complete binary tree where the parent node is always compared to its children according to a specific order (max-heap or min-heap).
- In a max-heap, for any given node I, the value of I is greater than or equal to the values of its children. The relationship between siblings is not defined.
- The relationship between parent and child indices (assuming a 1-based index):
- Left Child Index = (Parent Index) * 2
- Right Child Index = (Parent Index) * 2 + 1
- Parent Index = (Child Index) / 2
Min & Max Heap
- Implemented using a binary tree, a heap can be viewed as a priority queue where elements are served based on their priority.
- In a max-heap, the parent node is always greater than its children.
- Index relationships (assuming 0-based index):
- To Parent: (index - 1) / 2
- Left Child: 2 * index + 1
- Right Child: 2 * index + 2
- The time complexity to build a heap is O(n).
1
2
3
4
5
6
7
8
import heapq
nums = [9, 7, 5, 3, 1]
heapq.heapify(nums) # Result: nums == [1, 3, 5, 9, 7]
heapq.heappop(nums) # Output: 1
heapq.heappush(nums, 10)
heapq.heappushpop(nums, 11) # More efficient than push then pop separately
Heap
- 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조이다.
- 힙의 특징에는 최대힙일 경우 항상 부모가 자식보다 커야하고 형제간의 관계는 보지 않는다.
- 힙에서의 부모 노드와 자식 노드의 관계(index가 1부터 시작한다고 했을 때)
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = (자식의 인덱스) / 2
Min & Max Heap
- 바이너리 트리로 구현이 된다. 이것은 priority queue라고 볼 수 있다. 일정한 우선순위에 의해 나오게 되는 것을 의미한다.
- Max heap의 경우 부모 노드는 항상 자식들 보다 크게 된다.
- To parent: (index-1)/2
- Left child: 2*index + 1
- Right child: 2*index + 2
- 힙을 만드는데 필요한 time은 O(n)
1
2
3
4
5
6
7
8
import heapq
nums = [9,7,5,3,1]
heapq.heapify(nums) # nums == [1,3,5,9,7]
heapq.heappop(nums) # output: 1
heapq.heappush(nums, 10)
heapq.heappushpop(nums, 11) # more efficiently peappush() then heappop()
