[자료구조] 힙

[자료구조] 힙

1. 정의

• 이진 트리 구조로 이루어져 있다.
  • 최대값과 최소값을 빨리 찾아낼 수 있다.
• 최대 힙
  • 항상, 자식 노드 < 부모 노드 관계를 만족해야 한다.
• 최소 힙
  • 항상, 자식 노드 > 부모 노드 관계를 만족해야 한다.
• 노드의 개수를 n이라고 하면 트리의 높이는 $log_2(n+1) - 1$로 구할 수 있다.

2. 추가 제거

이제부터 최대 힙 기준으로 설명하겠습니다.

• 추가
  1. 비어있는 공간에 노드를 추가한다.
  2. 부모 노드보다 자식 노드가 더 크면 두 노드의 자리를 바꾼다.

  public void add(E obj) {
      array[++lastposition] = obj; // 1. 노드 추가
      trickleUp(lastposition); // 2. trickle up - 부모 노드와 자식 노드를 바꿀지 말지 선택하는 함수
  }

  public void trickleUp(int position) {
      if (position == 0) {
          return;
    }
      int parent = (int) Math.floor((position - 1) / 2)
      if (((Comparable<E>) array[position]).compareTo(array.parent) > 0) {
          swap(position, parent);
          trickleUp(parent);
      }
  }

  public void swap(int from, int to) {
      E tmp = array[from];
      array[from] = array[to];
      array[to] = tmp;
  }

• 제거
  1. 루트를 제거한다
  2. 트리의 마지막 요소를 루트에 집어 넣는다.
  3. 루트가 자식 노드보다 작다면 두 자식 노드 중 큰 수와 자리를 바꾼다.

public E remove() {
    E tmp = array[0];
    swap(0, lastposition--); // 루트와 마지막 노드를 바꿔주고 lastposition을 줄여 배열에서 제거합니다.(remove를 계속 실행하면 오름차순의 배열이 만들어짐 (힙 정렬, O(nlogn)))
    trickleDown(0);
    return tmp;
}

public void trickleDown(int parent) {
  //자식들의 주소 찾기
    int left = 2 * parent + 1;
    int right = 2 * parent + 2;

    if (left == lastposition && (((Comparable<E>) array[parent]).compareTo(array[left]) < 0) {
        swap(parent, left); 
        return;
    }

    if (right == lastposition && (((Comparable<E>) array[parent]).compareTo(array[right]) < 0) {
        swap(parent, right); 
        return;
    }

    if (left >= lastposition || right >= lastposition) {
        return;
    }

    if (array[left] > array[right] && array[parent] < array[left]) {
        swap(parent, left);
        trickleDown(left);
    } else if (array[parent] < array[right]) {
        swap(parent, right);
        trickleDown(right);
    }
}

---

※ 참조

• 자바로 구현하고 배우는 자료구조 - 네이버 부스트 코스

• Interview_Question_for_Beginner