최대힙
-
[간단 정리] 힙 정렬알고리즘/프로그래머스 2019. 11. 27. 21:10
* 오름차순 기준입니다 생각보다 쉽지 않았다. 처음에 개념을 잘못 잡는 바람에 완전히 이해하기까지 반나절 정도 걸렸다. 현상을 이해하는 방식이 꽤 자주 스스로도 특이하다고 느껴질 때가 있다. 친절하게 설명하려면 그림을 곁들여야 하는데, 바람은 언제나 텍스트만으로 마무리 짓는 것이다. 그러기 위해서는 두괄식으로 설명해야 할 듯하다. 힙은 자료구조로서 '키'의 우선 순위가 있을 때 유용하다. 기본적으로 완전 이진 트리다. 트리의 왼쪽부터 데이터가 삽입되기 때문에 배열을 이용하면 매우 편하다. 순차적으로 인덱스를 활용할 수 있기 때문. 데이터는 키를 통해 최대 힙 혹은 최소 힙으로 정렬한다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 속성이다. 최대 ..