힙의 개념

• 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조

• 최대 힙max heap

  • 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리

  • {부모 노드의 키값 ≥ 자식 노드의 키값}

  • 루트 노드 : 키값이 가장 큰 노드

• 최소 힙min heap

  • 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리

  • {부모 노드의 키값 ≤ 자식 노드의 키값}

  • 루트 노드 : 키값이 가장 작은 노드

• 

힙의 예

힙이 아닌 예

힙의 삽입 연산

• 1. 완전 이진 트리의 조건이 만족하도록 다음 자리를 확장

  • 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드

  • n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장

• 2. 부모 노드와 크기 조건이 만족하도록 삽입 원소의 위치를 찾음

  • 현재 위치에서 부모 노드와 비교하여 크기 관계를 확인

  • {현재 부모 노드의 키값 ≥ 삽입 원소의 키값}의 관계가 성립하지 않으면, 현재 부모 노드의 원소와 삽입 원소의 자리를 서로 바꿈

• 힙의 삽입 연산 예1) 17을 삽입하는 경우

  • 노드를 확장하여 임시로 저장한 위치에서의 부모 노드와 크기를 비교하여 힙의 크기관계가 성립하므로, 현재 위치를 삽입 원소의 자리로 확정

    

• 힙의 삽입 연산 예2) 23을 삽입하는 경우

  

힙의 삭제 연산

• 힙에서는 루트 노드의 원소만 삭제할 수 있음

• 1. 루트 노드의 원소를 삭제하여 반환

• 2. 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정

  • 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 위해서 마지막 노드, 즉 n번 노드를 삭제

  • 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장

• 3. 완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리를 찾음

  • 현재 위치에서 자식 노드와 비교하여 크기 관계를 확인

  • {임시 저장 원소의 키값 ≥ 현재 자식 노드의 키값 }의 관계가 성립하지 않으면, 현재 자식 노드의 원소와 임시 저장 원소의 자리를 서로 바꿈

• 힙의 삭제 연산 예