0
위키 피 디아에 따르면, 이것은 최소 힙 : https://en.wikipedia.org/wiki/Min-max_heap입니다. O (n)에서 min-max 힙을 만드는 방법이 있는지 궁금합니다. 나는 당신이 min heap과 max heap 모두를 가지고 이것을 할 수 있다는 것을 알고 있지만, 나는 이것이 어떤 접근법이 될지 모르겠다. 요소를 삽입하는 것은 O (log n) 시간의 복잡성을 필요로하며 이런 종류의 트리는 O (n log n)보다 효율적으로 빌드 할 수없는 것처럼 느껴지지만 누군가가 대답을하기를 바랍니다. 감사.O (n) 시간 복잡도에서 최소 최대 힙 빌드
위키피디아의 기사에 따르면 Floyd의 O (n) 알고리즘을 사용하여 최소 최대 힙을 만들 수 있다고 나와 있습니다. 왜 알고리즘이 O (n)인지 설명하는 데 도움이되는 참고 자료도 있습니다. – rici
나는 그 alogirthm을 정말로 이해하려고 노력했다. 그러나 방금 알고리즘을 공부하기 시작 했으므로 이해하기가 어렵다. 그래서 나는 여기서 도움을 얻기를 바라고있다. – Cherry
간단한 알고리즘을 이해하는 가장 좋은 방법은 연필과 종이입니다. 일부 입력에서 사용해보십시오. 그러면 어떻게 작동하는지 볼 수 있습니다. (이것은 heaport 알고리즘에서 힙을 빌드하는 데 사용되는 것과 동일한 접근법이므로 작업하기가 더 쉽습니다.) – rici