[Algorithm] 자료구조 - 힙(Heap)과 우선순위 큐(Priority Queue)

 

우선순위 큐(Priority Queue)

---

일반적인 큐는 조건 없는 FIFO(First-In-First-Out) 구조이지만,

우선순위 큐(Priority Queue)는 우선순위에 따라 특별한 순서로 원소를 추출하는 것이다

이진 힙 자료구조로 구현한다

 

 

힙 (Heap)

---

레코드는 배열에 저장하며,

모든 노드는 부모의 값이 자식 값보다 크다(또는 작다)는 동일한 규칙을 따르는 자료 구조

완전 이진 트리(complete binary tree)를 기본으로 한다

💡 이진 트리 : codesyun.tistory.com/112

[Algorithm] 트리 (Tree), 이진 트리(Binary tree)

 

 

힙의 유형

---

1. 최대 힙(Max heap) : 각 노드의 값은 자식 노드의 값 이상

2. 최소 힙(Min heap) : 각 노드의 값은 자식 노드의 값 이하

 

 

힙의 특징

---

- 데이터에서 최댓값, 최솟값을 하나씩 가져올 때 유용한 구조

- 힙 정렬은 힙을 사용해 오름차순 또는 내림차순으로 데이터를 정렬한다

 

 

힙의 API

API (Appication Programming Interface)

---

- Insert(k)

    * 힙에 새 원소 k를 추가

    * 시간 복잡도는 O(logn)

 

- Remove()

    * 최대 힙일 때 최대값을, 최소 힙일 때 최솟값을 추출

    * 시간 복잡도는 O(logn)

 

- Heapify()

    * 숫자 배열을 힙으로 변환

    * 시간 복잡도는 O(n)

 

 

 

💡 자료 구조 : codesyun.tistory.com/106

[Algorithm] 자료 구조(Data Structure) 란?