힙

• 힙

  • 대표적인 우선순위 큐로, 완전 이진 트리라는 구조를 사용한다.
  • 힙에서 사용하는 트리는 위에서 아래로 부모-자식관계로 매달린 것을 말한다.

• 트리

  • 그래프 이론에서 "싸이클을 만들지 않는 연결된 그래프"

  • 맨 위의 노드는 루트라고 한다.

  • 이진 트리

    이진 트리 예시
    

  • 모든 노드가 2개 이하의 자식을 갖는 트리

  • 포화 이진 트리

    • 루트로부터 시작해 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리를 말한다.
    • 포화 이진 트리가 되려면 노드의 총 수가 1, 3, 7, 15, 31 ...과 같이 2^k - 1개가 되어야 한다.

  • 리프 노드

    • 말단 노드라고도 하는데, 자식이 하나도 없는 노드를 말한다.

  • 완전 이진 트리

    • 노드 수가 맞지 않아 포화 이진 트리를 만들 수 없을 때 최대한 포화 이진 트리에 가깝게 만든 것이다
    • 루트로부터 시작해서 모든 노드가 자식을 2개씩 가지면서 내려가는 것은 동일하다.

힙의 조건

• 완전 이진 트리
• 힙 특성 만족
  • 모든 노드는 값을 갖는다.
  • 모든 노드는 자식 노드(들) 값보다 크다.

• 힙 특성을 만족하면 우선순위가 가장 큰 원소가 루트에 자리하게 된다. (최대 힙)
• 위와 반대인 최소 힙도 존재한다.
• 리스트는 기초적인 자료구조지만 완전 이진 트리를 표현하는 데는 안성맞춤이다.
  • 리스트가 A[0]로 시작된다면 자식은 A[2k+1]과 A[2k+2]이다.
  • 완전 이진 트리라 중간에 빠지는 노드가 없이 자식들을 꽉 채우는 성질로 인해 이처럼 리스트의 인덱스로 간단히 계산할 수 있다.

힙 객체의 구조

• __A[] 🠔 힙을 저장하는 리스트
  
  
• insert() 🠔 힙에 원소 x를 삽입한다.
• deleteMax() 🠔 힙의 최대 원소를 알려주면서 삭제한다.
• max() 🠔 힙의 최대 원소를 알려준다.
• buildHeap() 🠔 리스트 A[]를 힙으로 만든다.
• isEmpty() 🠔 힙이 비었는지 알려준다.
• clear() 🠔 힙을 깨끗이 청소한다.

힙 수행 시간

• 원소 삽입
  • O(logN), 운이 좋으면 Θ(1)
• 원소 삭제
  • O(logN), 운이 좋으면 Θ(1)
• 힙 생성
  • Θ(n)

Code

Github