히프에서 원소를 삭제하는 연산은 언제나 루트 노드에 있는 원소를 삭제하여 반환한다. 따라서 최대 히프에서 수행하는 삭제 연산은 키값이 가장 큰 원소를 삭제하여 반환하는 연산이 되고, 최소 히프에서 수행하는 삭제 연산은 키값이 가장 작은 원소를 삭제하여 반환하는 연산이 된다. 히프의 삭제 연산에서 중요한 것은 루트 노드의 원소를 삭제한 후에도 완전 이진 트리의 형태와 노드의 키값에 대한 히프의 조건이 유지되어야 한다는 것이다.

레스토랑에서 테이블을 하나 치워야 한다면 그 테이블에 앉아 있던 사람들은 일단 빈 테이블로 옮겨 앉아 있다가 적당한 자리가 생기면 그 자리로 옮기고, 그리고 나서 좀 더 좋은 자리가 생기면 다시 자리를 옮길 것이다.

마찬가지로 [ 그림 7-58 ] 의 ①에서 루트 노드의 원소를 삭제한 후에도 전체 노드의 개수가 하나 줄어든 완전 이진 트리여야 하므로 마지막 노드, 즉 6번 노드의 자리를 제거해야 한다. 그러면 마지막 6번 노드에 있던 원소 10은 갈 곳이 없으므로 ②와 같이 비어 있는 루트 노드에 임시로 저장한다. 일단 완전 이진 트리 형태를 유지했으므로 이제는 키값의 관계가 최대 히프가 되도록 조정한다. 임시로 루트 노드에 옮겨 놓은 원소의 키값과 현재 위치에서의 왼쪽 자식 노드의 키값과 오른쪽 자식 노드의 키값을 비교하여 키값이 가장 큰 원소가 부모 노드가 되도록 자리를 바꿔 준다. ③에서 루트로 옮겨진 노드의 키값 10이 현재 위치에서의 자식 노드의 키값 19보다 작으므로 자리를 맞바꾼다. ④와 같이 옮겨진 자리에서 최대 히프의 조건을 만족하는지 검사하기 위해 옮겨진 노드의 키값 10과 현재 위치에서의 자식 노드의 키값 8과 13을 다시 비교하는데, 자식 노드의 키값 13이 가장 크므로 노드 10과 자리를 바꾼다. ⑤ 더 이상 크기를 비교할 자식 노드가 없으므로 현재의 자리가 노드 10의 자리로 확정되어 최대 히프의 재구성 작업을 완성하고 삭제 연산을 종료한다.

[ 알고리즘 7-12 ] 는 1차원 배열의 순차 자료구조를 이용한 최대 히프에서의 삭제 연산을 정의한 알고리즘이다.

① 루트 노드 heap[1]을 변수 item에 저장한다.

② 마지막 노드의 원소 heap[n]을 변수 temp에 임시로 저장한다.

③ 마지막 노드를 삭제하였으므로 히프 배열의 원소 개수가 하나 감소한다.

④ 마지막 노드의 원소였던 temp의 임시 저장 위치 i는 루트 노드의 자리인 1번이 된다.

⑤ 현재 저장 위치에서 왼쪽 자식 노드 heap[j]와 오른쪽 자식 노드 heap[j+1]이 있을 때, 키값이 큰 자식 노드의 키값과 temp를 비교하여 temp가 크거나 같으면 현재의 임시 저장 위치를 temp 자리로 확정하고, ⑦을 수행한다.

⑥ temp가 자식 노드 heap[j]보다 작으면 자식 노드와 자리를 바꾸고 ⑤~⑥을 반복하면서 temp의 자리를 찾는다.

⑦ 찾은 위치에 temp를 저장하여 최대 히프의 재구성 작업을 완성한다.

⑧ 처음에 삭제된 루트 노드를 저장한 변수 item을 반환하고 삭제 연산을 종료한다.