배열을 사용한 이진 힙의 생성 바로 가기

Question

배열을 오름차순으로 정렬하면 이진 힙이 생성됩니다. 이 장점의 단점이 있습니까? 그렇다면 그 이유는 무엇입니까?

Answer 1

"배열을 오름차순으로 정렬하면 바이너리 힙이 생깁니다." 이 말이 맞습니다. 이제 배열을 오름차순으로 정렬하는 알고리즘에 따라 다릅니다. 최상의 정렬 알고리즘은 복잡도가 O(NLogN) 인 것으로 수행하십시오.

알고리즘 Build_Heap은 단지 이진 힙을 만들 때 O(N)의 복잡성을 갖지만.

Counting Sort과 같은 비 비교 기반 정렬 방법을 사용할 때까지는 이진 힙 생성을위한 복잡성이 최소한 O(NLogN) 및 atmost O(N^2)입니다.

기존의 바이너리 힙 생성 방법이 유리합니다. Counting Sort하지만

는 O(N) 시간이 걸릴 것입니다하지만 전통 Build_Heap은 현재 위치에서 바이너리 힙 을 만들 것 동안은 여분의 공간 O(N)이 필요합니다.