[자료구조] 힙 삭제

 

힙 삭제

• 힙에 있는 데이터를 삭제하는 것
• O(log N)
• 최소 힙(Min Heap) 삭제, 최대 힙(Max Heap) 삭제가 있다. 

 

 

최소 힙(Min Heap) 삭제 

1. 그래프가 최소 힙인지 아닌지 확인
   1. 완전 이진 트리인지 확인
   2. 각 노드의 값이 자식 노드의 값보다 작거나 같은지 확인
2. 힙의 가장 아래에 있는 리프 노드값을 루트 노드에 덮어씌운다.
3. 힙 가장 아래에 있는 리프 노드값을 삭제한다. 
4. 수정된 루트 노드가 최소 힙 조건을 만족하는지 확인한다. 
   1. 루트 노드가 최소 힙 조건을 만족하지 않으면, 자식 노드와 위치를 바꾼다.
   2. 바뀐 위치에서 최소 힙 조건을 만족하는지 확인한다. 
      1. 바뀐 위치에서 최소 힙 조건을 만족하지 않으면, 자식 노드와 위치를 바꾼다. 
5. 최소 힙 조건을 만족하면 종료한다. 

 

루트노드 값을 10으로 덮어씌우기.

리프 노드 삭제

루트 노드 값과 자식 노드 값 바꾸기.

루트 노드 값과 자식 노드 값 바꾸기.

 

 

 

최대 힙(Max Heap) 삭제

1. 그래프가 최대 힙인지 확인
   1. 완전 이진 트리인지 확인
   2. 각 노드의 값이 자식 노드의 값보다 크거나 같은지 확인
2. 힙 가장 아래에 있는 리프 노드 값을 루트 노드에 덮어씌운다. 
3. 힙 가장 아래에 있는 리프 노드 값을 삭제한다. 
4. 수정된 루트 노드가 최대 힙 조건을 만족하는지 확인한다. 
   1. 루트 노드가 최대 힙 조건을 만족하지 않으면, 자식 노드와 위치를 바꾼다. 
   2. 바뀐 위치에서 최대 힙 조건을 만족하는지 확인한다. 
      1. 바뀐 위치에서 최대 힙 조건을 만족하지 않으면, 자식 노드와 위치를 바꾼다. 
5. 최대 힙 조건을 만족하면 종료한다. 

 

루트노드 값을 4으로 덮어씌우기.

리프 노드 삭제

 

루트 노드 값과 자식 노드 값 바꾸기.