힙은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다) 을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조다.

앞서 우리가 우선순위 큐를 사용할 때 매번 활용했던 heapq모듈이 바로 힙으로 구현되어있다. 그리고 힙은 배열로 구현한다.

따라서 우선순위 큐는 결국 배열로 구현하는 것

힙은 좌우에 대한 관계는 정의되어있지 않다. 즉 정렬된 구조가 아니다.

힙은 완전 이진트리로 순서대로 표현하기에 적합 . 완전 이진 트리 형태인 이진 힙은 배열에 배치가 가능하며 계산의 편의를 위해 인덱스는 1부터 사용한다.

아까 언급했듯이 힙 덕분에 다익스트라 알고리즘의 시간 복잡도가 줄 수 있었으며 이외에도

힙정렬

최소 신장 트리를 구현하는 프릴 알고리즘

중앙값의 근사값을 빠르게 구하기

등등 에 활용된다.