heap의 정의

max heap의 정의

max heap에 임의의 키 값을 가지는 노드를 삽입

  1. max heap은 완전 이진 트리이므로 새로운 노드는 완전 이진 트리의 마지막 노드 다음 위치에 삽입된다.
  2. 삽입된 노드와 그 부모 노드의 키 값을 비교한다. 삽입된 노드의 키 값이 부모 노드의 키 값보다 크면 두 노드의 위치를 바꾼다.
  3. 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 작아질 때까지 2단계를 반복한다.

    <키값이 5와 40인 노드를 삽입하는 예>

    그림을 마우스로 클릭하세요.

max heap에서 가장 큰 키 값을 가지는 노드를 삭제

  1. max heap의 루트에는 가장 큰 키 값을 가지는 노드가 들어있으므로 루트 노드를 삭제한다.
  2. 빈 루트 노드 자리에는 완전 이진 트리의 마지막 노드를 삽입한다.
  3. 삽입된 노드와 그 자식 노드의 키 값을 비교한다. 삽입된 노드의 키 값이 자식 노드의 키 값보다 작으면 두 노드의 위치를 바꾼다.
  4. 삽입된 노드의 키 값이 자신의 자식 노드 키 값보다 커질 때까지 3단계를 반복한다.

    <키값이 30과 3인 노드를 삽입하는 예>

    그림을 마우스로 클릭하세요.

min heap의 정의

min heap에 임의의 키 값을 가지는 노드를 삽입

  1. min heap은 완전 이진 트리이므로 새로운 노드는 완전 이진 트리의 마지막 노드 다음 위치에 삽입된다.
  2. 삽입된 노드와 그 부모 노드의 키 값을 비교한다. 삽입된 노드의 키 값이 부모 노드의 키 값보다 작으면 두 노드의 위치를 바꾼다.
  3. 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 작으면 두 노드의 위치를 바꾼다.
  4. 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 커질 때까지 2단계를 반복한다.

    <키 값이 70과 5인 노드를 삽입하는 예>

    그림을 마우스로 클릭하세요

min heap에서 가장 작은 키 값을 가지는 노드를 삭제

  1. min heap의 루트에는 가장 작은 키 값을 가지는 노드가 들어있으므로 루트 노드를 삭제한다.
  2. 빈 루트 노드 자리에는 완전 이진 트리의 마지막 노드를 삽입한다.
  3. 삽입된 노드의 그 자식 노드의 키 값을 비교한다. 삽입된 노드의 키 값이 자식 노드의 키 값보다 크면 두 노드의 위치를 바꾼다.
  4. 삽입된 노드의 키 값이 자신의 자식 노드 키 값보다 작아질 때까지 3단계를 반복한다.

    <키 값이 5와 70인 노드를 삭제하는 예>

    그림을 마우스로 클릭하세요

min-max heap의 정의

  1. min-max heap은 완전 이진 트리이며 min 레벨과 max 레벨이 차례로 반복된다.
  2. 루트는 min 레벨로 시작한다.
  3. min 레벨의 노드는 그 노드의 모든 후손들보다 작은 키 값을 가진다.
  4. max 레벨의 노드는 그 노드의 모든 후손들보다 큰 키 값을 가진다.
  5. min heap이나 max heap은 가장 작은 키 값을 가지는 노드는 가장 큰 키 값을 가지는 노드만을 찾기에 적합하도록 되어있지만 min-max heap은 두가지 노드를 모두 찾기에 적합한 자료 구조이다.

min-max heap에 임의의 키 값을 가지는 노드를 삽입

  1. min-max heap은 완전 이진 트리이므로 새로운 노드는 완전 이진 트리의 마지막 노드 다음 위치에 삽입된다.
  2. 삽입된 노드가 어느 레벨에 있는지 검사하고, 삽입된 노드와 그 부모 노드의 키 값을 비교한다.
  3. 새로운 노드가 어느 레벨에 있는지 검사하고, 삽입된 노드의 키 값이 부모 노드의 키 값보다 작으면 삽입된 노드의 키 값과 같은 min 레벨에 있는 조부모 노드의 키 값을 비교한다.
  4. 삽입된 노드의 키 값이 조부모 노드의 키 값보다 작으면 두 노드를 바꿔준다.
  5. 변경된 노드의 키 값이 조부모 노드의 키 값보다 클 때까지 4단계를 반복한다.
  6. 새로운 노드가 min 레벨에 삽입되고, 삽입된 노드의 키 값이 부모 노드의 키 값보다 크면 두노드를 바꿔준다.
  7. 변경된 노드의 키 값과 같은 max 레벨에 있는 조부모 노드이 키 값을 비교한다.
  8. 변경된 노드의 키 값이 조부모 노드의 키 값보다 크면 두 노드를 바꿔준다.
  9. 변경된 노드의 키 값이 조부모 노드의 키 값보다 작을 때까지 7,8단계를 반복한다.
  10. 새로운 노드가 max 레벨에 삽입되고 삽입된 노드의 키 값이 부모 노드의 키 값보다 크면 삽입된 노드의 키 값과 같은 max 레벨에 있는 조부모 노드의 키 값을 비교한다.
  11. 삽입된 노드의 키 값이 조부모 노드의 키 값보다 크면 두 노드를 바꿔준다.
  12. 변경된 노드의 키 값이 조부모 노드의 키 값보다 작을 때까지 11단계를 반복한다.
  13. 새로운 노드가 max 레벨에 삽입되고, 삽입된 노드의 키 값이 부모 노드의 키 값보다 작으면 두 노드를 바꿔준다.
  14. 변경된 노드의 키 값과 같은 min 레벨에 있는 조부모 노드의 키 값을 비교한다.
  15. 변경된 노드의 키 값이 조부모 노드의 키 값보다 작으면 두 노드를 바꿔준다.
  16. 변경된 노드의 키 값이 조부모 노드의 키 값보다 클 때까지 14,15단계를 반복한다.

    <키 값이 5와 95인 노드를 삽입하는 예>

    그림을 마우스로 클릭하세요

min-max heap에서 최소 키 값을 가지는 노드를 삭제

  1. min-max heap의 루트에는 최소키 값을 가지는 노드가 있으므로 루트 노드를 삭제한다.
  2. 빈 루트 노드 자리에는 완전 이진 트리의 마지막 노드를 삽입한다.
  3. 삽입된 노드와 자식 노드및 손자 노드의 키 값을 비교한다.
  4. 자식 노드는 max 레벨에 있으므로 삽입된 노드의 키 값이 자식 노드의 키 값보다 큰 경우는 삽입될 노드가 그 노드를 포함한 모든 후손들보다 큰 키 값을 가지게 된다. 따라서 삽입된 노드와 자식 노드를 바꿔준다.
  5. 손자 노드는 같은 min 레벨에 있으므로 삽입된 노드의 키 값이 손자 노드의 키 값보다 큰 경우는 두 노드를 바꿔준다.
  6. 더이상 바꿀 노드가 없을때까지 3-5단계를 반복한다.

    <최소 키 값을 가지는 노드를 삭제하는 예>

    그림을 마우스로 클릭하세요

min-max heap에서 최대 키 값을 가지는 노드를 삭제

  1. min-max heap의 루트의 자식 노드를 중에 하나는 최대 키 값을 가지는 노드이다 따라서 두 노드중에 큰 키 값을 가지는 노드를 삭제한다.
  2. 빈 자리에는 완전 이진 트리의 마지막 노드를 삽입한다.
  3. 삽입된 노드와 자식 노드및 손자 노드의 키 값을 비교한다.
  4. 자식 노드는 min 레벨에 있으므로 삽입된 노드의 키 값이 자식 노드의 키 값보다 작은 경우는 삽입된 노드가 그 노드를 포함한 모든 후손들보다 작은 키 값을 가지게 된다. 따라서 삽입된 노드와 자식 노드를 바꿔준다.
  5. 손자 노드는 같은 max 레벨에 있으므로 삽입된 노드의 키 값이 손자 노드의 키 값보다 작은 경우는 두 노드를 바꿔준다.
  6. 더이상 바꿀 노드가 없을때까지 3-5단계를 반복한다.

    <최대 키 값을 가지는 노드를 삭제하는 예>

    그림을 마우스로 클릭하세요

deap의 정의

deap에 임의의 키 값을 가지는 노드를 삽입

  1. deap은 완전 이진 트리이므로 새로운 노드는 완전 이진 트리의 마지막 노드 다음 위치에 삽입된다.
  2. 삽입된 노드의 키 값과 반대편 서브트리의 대응하는 노드의 키 값을 비교한다.
  3. 왼쪽 서브트리 (min heap)에서의 노드의 키 값이 대응하는 오른쪽 서브트리(max heap)에서의 노드의 키 값보다 크면 두 노드를 바꿔준다.
  4. 새로 노드가 삽입된 서브트리에서는 min heap이나 max heap에 새로운 노드가 삽입된 것과 같으므로 min heap의 노드 삽입 방법이나 max heap의 노드 삽입 방법에 따라 처리해준다.

    그림을 마우스로 클릭하세요

deap에서 최소 키 값을 가지는 노드를 삭제

  1. deap루트의 왼쪽 서브트리인 min heap에서 루트 노드를 삭제한다.
  2. deap의 마지막 노드를 빈 자리에 삽입한다.
  3. min heap에서 최소 키 값 노드 삭제 방법에 따라 삽입된 노드의 키 값과 그 자식 노드의 키 값을 비교하여 삽입된 노드이 키 값이 큰 경우는 두 노드를 차례로 바꿔준다.
  4. min heap이 정의되면 삽입된 노드의 최종 위치에 대응하는 max heap노드를 찾아서 두 노드의 키 값을 비교한다.
  5. min heap노드의 키 값이 max heap노드의 키 값보다 크면 두 노드를 바꿔준다.

    그림을 마우스로 클릭하세요

deap에서 최대 키 값을 가지는 노드를 삭제

  1. deap루트의 오른쪽 서브트리인 max heap에서 루트 노드를 삭제한다.
  2. deap의 마지막 노드를 빈 자리에 삽입한다.
  3. min heap에서 최대 키 값 노드 삭제 방법에 따라 삽입된 노드의 키 값과 그 자식 노드의 키 값을 비교하여 삽입된 노드이 키 값이 작은 경우는 두 노드를 차례로 바꿔준다.
  4. max heap이 정이되면 삽입된 노드의 최종 위치에 대응하는 min heap노드를 찾아서 두노드의 키 값을 비교한다.
  5. max heap노드의 키 값이 min heap노드의 키 값보다 작으면 두 노드를 바꿔준다.

    그림을 마우스로 클릭하세요