우선순위 큐와 힙(heap) (3) 힙의 삽입, 삭제연산

이전 글에서 힙을 정의하는 코드에 대해 설명했다.

 

이번에는 삽입, 삭제 연산에 대한 코드를 작성해보자.

 

먼저 삽입 연산.

 

코드는 다음과 같다. 한번 직접 머릿속으로 코드를 굴려보자.

가령 내가 5의 우선순위를 가지는 heap을 새로 삽입할 때 insert_heap(5); 로 삽입한다.

is_full_heap() 함수에 의해 heap이 꽉 찬 경우 5는 삽입되지 못하고 함수는 종료된다.

 

꽉차지 않은 경우 먼저 heap_size의 값을 1더하고 그 값을 i에 넣는다.

 

이해를 돕기 위해 이전 글에서 썻던 이미지를 사용하자.

현재 마지막 heap의 index는 10이고 그 Key(우선순위)값은 3이다. 따라서 heap_size=10이다. 일단 새로운 heap을 추가하는 경우 index가 11에 삽입 되어야한다. 그래서 i=++(heap_size); 의 코드를 쓰는 것이다.

 

11번 째에 Key값이 5인 heap이 들어갔으므로 부모 노드들 5번 heap(key=4), 2번 heap(key=7), 1번 heap(key=9)와 그 값을 비교해야한다. 하지만 계산 속도를 높이기 위해 while문으로 새로 들어온 key값이 적당한 위치에 도달했거나(=부모 heap의 key값이 더 큰 경우에 더 이상의 이동은 불필요한 것이 되므로), index값이 1에 도달한 경우 while문이 끝난다.  (i=1인 경우 위에 더 이상의 부모 heap이 존재하지 않으므로 종료한다.)

 

while문의 코드를 좀 더 자세히보자

 

while의 조건은 위에서 충분히 설명했고, 내부 연산을 보자. heap[i] = Parent(i);를 통해 부모1 key값을 자식위치로 옮긴다.

그리고 i값이 부모1의 값으로 바뀌고 다시 while문 실행. 조건이 참이라면 heap[i] = Parent(i); 코드를 통해 부모1의 부모 heap인 부모2의 key값을 부모1의 key값으로 또 옮긴다. 그냥 위에서 한칸씩 덮어 쓰기로 내리는 모습이라고 보면 된다.

 

while문이 끝났을 때는 다음과 같은 상태가 된다. 부모의 key값인 4가 i=11의 자리에 가 있고 변수 n에 저장된 기존의 key값인 5가 while문이 끝나고 해당하는 index heap의 key값에 삽입되는 것이다.

 

 

마지막으로 삭제연산.

 

다음에 마저 작성하겠다.