Heap과 이진검색

이 글을 쓰게된 이유는 알고리즘 문제를 풀다가 아래와 같은 생각이 들었다.

자료구조인 Heap을 사용하는 대신 이진검색을 이용하여 컨테이너에 값을 삽입하면 힙과 같을까?

결론을 말하자면 Heap은 이진검색을 사용할 때 보다 효율적이다. 그런데 생각해보면 Heap은 max heap/min heap 모두 사입/삭제에 log(N)이 사용되고 이진검색도 배열에서 값을 찾기위해 log(N)의 연산이 사용된다. 그러나 이 둘의 차이는 Heap은 완전이진트리 구조라는 것이다. 완전이진트리인 Heap은 최악의 경우에도 log(N)이 걸리지만 이진검색은 최악의 경우 N의 연산이 사용된다. 자세한 내용은 ChatGPT가 정리한 것을 참고하면 된다.

 

완전이진트리 VS 이진검색

https://chat.openai.com/share/c64c3bb7-266e-43f3-b656-6f816132bfa1