[알고리즘] 힙, 힙정렬

1. 힙 자료구조

0. 개념

- max heap, min heap ((a)트리 형태의 자료구조로 설명하지만, 실제로는  (b)1차원 배열 형태로 표현)

2009 Introduction to Algorithms Third Ed.

- 인덱스는 위치에 따라 고정되어 있는 느낌,,

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

- max heap에서, 부모가 자식보다 크거가 같은 것은 보장되지만, 자식 간 대소비교는 인덱스로 구분하기 어려움. 

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

 

2. 주요 쓰임 두 가지:

(1) 힙 정렬 (2) 우선순위 큐

 

 

3. Building heap

3-1. 원소 삽입 push : 마지막 노드에 삽입 

→ 힙 성질 만족할 때까지 부모 노드와 swap (아래→위의 Bottom Up 방식)

→ 반복 반복...

 

3-2. 원소 삭제 pop : max heap에서 원소를 삭제한다는 것은 root node(=최댓값)을 삭제한다는 것 

→ 최댓값을 미리 저장 후,

→ 삭제된 자리(root)에 마지막 노드 A를 가지고 옴 (=마지막 노드와 루트 노드를 swap)

→ 힙 성질 만족할 때까지(=A보다 더 큰 자식노드가 없을 때까지) A를 A의 더 큰 자식노드와 swap 반복...

    : 위→아래의 Top Down 방식

→ 미리 저장해둔 최댓값을 return시키고, heap의 크기를 1 감소시킴

 

 

---

2. 힙 정렬

1-1. 개념

max heap(내림차순)이나 min heap(오름차순) 자료구조를 활용하여 sorting하는 방법

 

1-2. 강점

- 시간 복잡도가 좋은 편

- 힙 정렬이 가장 유용한 경우는, 전체 자료를 정렬하는 것이 아니라, 가장 큰 값 몇 개만 필요할 때.

 

1-3. 방법

- 힙은 1차원 배열로 구현됨. 정렬해야 할 n개의 input들을 최대 힙 삽입을 통해 차례대로 삽입함.

(=즉 우리의 input으로 구성된 힙 자료구조를 직접 생성)

- 최대 힙으로 구성된 1차원 배열에서, 차례대로 삭제함 (=root에 있는 최댓값이 나옴)

- 그때마다 최대 힙 트리는 update됨 (힙의 성질 만족)

 

1-2. 복잡도

- 전체 t-c는 O(nlgn)

- Worst t-c는 omega(nlgn)

- 원소가 중복이 없을 때는 Best t-c가 omega(nlgn)

---

힙, 힙정렬 개념 야무지게 잘 정리된 페이지 링크 모음 🤩

 

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

[자료구조] 힙(heap)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

https://www.daleseo.com/python-heapq/

파이썬의 heapq 모듈로 힙 자료구조 사용하기

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

[자료구조] 힙(heap)