전체 정렬과는 다르다
최소 힙에서는 루트에 최솟값이 있지만 형제 노드 사이의 순서는 정해지지 않는다. 저장된 배열을 앞에서부터 읽는다고 값이 작은 순서로 나오는 것은 아니다. 힙은 필요한 극값을 빠르게 얻도록 부분적인 순서를 유지한다.
삽입과 제거 뒤의 복구
이진 힙에 새 원소를 넣으면 부모와 비교하며 적절한 위치로 올릴 수 있다. 루트를 제거한 뒤에는 마지막 원소를 옮겨 자식과 비교하며 내려보내는 방식으로 조건을 복구한다. 매번 전체 자료를 정렬할 필요는 없다.
우선순위 큐와의 관계
우선순위 큐는 우선순위에 따라 원소를 꺼내는 추상적 인터페이스다. 힙은 이를 구현하는 한 방법이다. 같은 우선순위의 원소를 넣은 순서대로 꺼내야 하는지는 별도로 정할 성질이며 일반적인 힙이 자동으로 보장하지는 않는다.
이진 힙에서의 비용
원소가 n개인 이진 힙은 보통 극값 조회에 O(1), 삽입과 루트 제거에 O(log n) 시간이 든다. 임의의 값이 어디 있는지 찾는 검색까지 같은 비용으로 빨라지는 것은 아니다. 알고리즘이 어떤 연산을 반복하는지에 따라 자료 구조를 골라야 한다.