[자료구조] Heap?

heap ?

우선순위 큐를 구현하기 위한 완전 이진 트리이다.

사실 이 글을 보는 사람들의 대부분은 Heap을 이미 알고 있는 사람일 것이다.
그래서 그냥 간단하게 외우기 쉽도록 중요한 것만 적고자 한다.

1. 왜 우선순위 queue를 heap으로 구현하냐?

   우선순위 queue를 구현하는 방법은 여러가지 있다. 예를들어 정렬된 리스트라던가.. 정렬된 연결리스트라던가...
   하지만 정렬된 리스트를 이용할 경우 삽입할 때 시간복잡도는? O(n)이 될 것이다.
   그렇다면 heap을 사용했을때 시간복잡도는? O(log n)이다.

   즉, 우선순위 큐를 구현하기에 heap이 적당하다고 볼 수 있다.

2. 제일 중요한 heap의 특성

   사실 이것만 좀 외우면 된다.

   부모 >= 자식

   이런 특성만 외우면 삽입과 삭제를 외울때 간편해진다.

   참고로 !! 헷갈릴수 있기때문에 미리 말하자면 BST랑 다른거다!!(참고로 나는 매일 헷갈린다.)
   BST는 왼쪽 < 부모 < 오른쪽 순으로 우선순위가 크다.
   눈치빠른 사람이라면 알겠지만 heap은 중복이 가능하고 BST는 중복이 불가능하다.

3. 삽입과 삭제
   heap의 특성을 외웠다면, 삽입과 삭제는 이것만 외워라

   삽입 -> 맨 뒤에 넣고 부모랑 계속 비교해
   삭제 -> 맨 앞에 빼고, 맨 뒤에걸 맨 앞에 넣어, 그리고 자식과 비교해

4. 구현
   일단 나는 구현을 배열로 할 것이다.. 이때 생각할 것은

   왼쪽 = 부모 2
   오른쪽 = 부모 2 + 1
   부모 = (왼 or 오) / 2

   이것만 알면 된다.

   📚 참고자료

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