이진 탐색 트리 외의 다른 트리 종류가 많다. 그 중 하나가 힙이라는 트리이다.
힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.
앞서 배웠던 큐는 First In, First Out 방식으로 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행한다. 즉, 큐의 데이터에 접근하려면 데이터가 삽입했던 순서에 우선권이 있다.
우선순위 큐는 삭제와 접근에 있어 전형적인 큐와 흡사하나, 삽입에 있어 정렬된 배열과 비슷한 리스트다. 즉, 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다.
병원 응급실의 중증도 분류체계 관리 애플리케이션을 예로 들어보자. 응급실에서는 도착한 순서대로 진료를 하는 것이 아니라, 중증도를 따져 진료한다.
중증도가 심한 순서대로 치료 (앞에서만 데이터에 접근하고 삭제)하고, 새로운 환자가 들어오면 중증도에 따라 적절한 순서를 매긴다 (삽입할 때는 늘 특정 순서대로 정렬)
우선순위 큐는 추상 데이터 타입으로, 기초적인 다른 자료 구조로 구현할 수 있다. 즉, 다음과 같은 제약을 가한 배열을 이용하면 된다.
배열 끝에서 삭제하니 O(1)이다. 하지만 삽입에는 정렬을 위해 검색을 먼저 해야하니 O(N)이 걸린다. 항목이 많아지면 삽입에 지연이 발생할 수 있다.
따라서 배열 기반 우선순위 큐는 삭제가 O(1) , 삽입이 O(N)이다.
우선순위 큐에서 정렬된 배열보다 효율적인 기반으로 쓰일 자료 구조가 힙이다.
힙에는 여러 종류가 있으나 주로 이진 합을 다룬다
이진 합은 특수한 종류의 이진 트리다. 이진 트리는 각 노드에 최대 자식 노드가 둘인 트리였다. 이진 힙에도 최대 힙과 최소 힙이라는 두 종류가 있으나 둘 간에 큰 차이는 없다.