인덱스를 0이 아닌 1부터 세는 이유
자식 노드에 접근하는 식의 변경이 있다.
구현을 단순화하기 위해 1부터 센다고 책에는 나오는데,
그렇게 복잡해지는지는 모르겠다.
삭제 연산할 때 리프 노드를 가져오는 이유
리프 노드는 삭제 되어도 대소 관계나 Heap 의 모양 규칙에 영향을 주지 않는다.
- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
- 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.
삽입과 삭제 모두, 처음에는 모양 규칙을 지키고 그 다음에 대소 관계 규칙에 따라 순서를 바꾼다.
Heap 의 생성을 O(N) 으로 하는 법
상향식 힙 생성은 Heap 에 삽입해야 되는 키가 모두 미리 주어졌을 때 O(N) 으로 가능하다고 한다.
참고: https://youngminieo1005.tistory.com/31
Heap 정렬의 효율
병합 정렬은 배열이 하나 더 필요하다.
Heap 정렬은 최대 원소를 배열의 마지막 칸에 삽입하면서 정렬되도록 구현하면 따로 공간이 필요없다.
시간 복잡도는 O(NlgN) 이다.
Heap 의 임의 원소 변경
Heap 에서 임의 원소를 변경하거나 삭제할 수 있다고 한다.
참고: http://www.secmem.org/blog/2020/08/16/heap/
마치며
[알고리즘 문제 해결 전략, 구종만 저] 를 읽다가 갑자기 의문이 든 부분을 정리해봤다.
Heap 생성을 O(N) 으로 할 수 있고, 임의 원소를 변경하는 방법이 있다는 점은 새로웠다.
