[자료구조] 힙 (Heaps)

Heap이란?

---

👉 개념

우선순위큐(Priority Queue)에서 사용되는 자료구조이며, 최대값이나 최솟값을 찾는 데 소요되는 시간이 O(1)이다.

하지만 노드 수정시, 힙구조 유지하기 위해 heapify과정을 거쳐 구조를 유지한다. 이는 결국 O(log n)의 시간 복잡도를 가진다.

 

👉 특징

Tree 중 배열에 기반한 완전 이진 트리 형식(왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리)을 가지며, 최대힙/최소힙 두 종류가 있다.

• 최대 힙 key(부모 노드) ≥ key(자식 노드)
• 최소 힙 key(부모 노드) ≤ key(자식 모드)

출처: https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

완전 이진 트리이기 때문에 삽입/삭제 연산이 배열의 가장 끝에서 발생한다. BST의 경우 삽입/삭제를 위해서 값을 찾아주는 과정이 필요했지만, 힙은 일단 배열의 맨 끝에서 수정이 이루어지기 때문에 BST보다 빠르다.

 

 

Leetcode 문제를 통한 Heap 구현

---

Python에서는 heapq를 통해 Heap을 구현할 수 있다. 해당 함수를 이용하는 방법과 직접 구현하는 방법을 통해 문제를 풀어볼 것이다. 

문제: https://leetcode.com/problems/relative-ranks/

Relative Ranks - LeetCode

 

1. Heapq 함수를 활용한 풀이

 

2. 직접 구현하여 완성한 풀이