힙

힙이란 뭘까 ? 🤔

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리이다.
  • 브랜치가 최대 2개이다. (이진)
  • 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. (완전)
• 최소값과 최소값을 찾으면 O(logn)이 걸린다.
  • 배열에서 최소값과 최대값을 찾으려면 O(n)이 걸리기때문에 힙이 훨씬 빠르다.
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

힙과 이진탐색 트리의 공통점과 차이점  🤔

• 차이점 ⇒ 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모노드, 그 다음 오른쪽 자식 노드 값이 가장 크지만 힙은 무조건 왼쪽부터 값을 집어넣는다.
  • 이진 탐색트리는 검색을 위한 구조이고, 힙은 최소값 최댓값을 구하기 위한 구조이다.
• 공통점 ⇒ 모두 이진트리이다. (최대 브랜치가 2개이다.)

최소 힙이냐, 최대 힙이냐에 따라서 추가적인 조건이 존재한다.

• 최대 힙 → 각 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙 → 각 노드의 값이 자식 노드의 값보다 작거나 같다.
  • 따라서 가장 크거나 작은 값은 루트 노드에 존재하게 된다.

힙의 기본 동작

데이터 삽입

• 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입이 된다.
• 최대힙이라면 조건이 하나 더 존재한다. 항상 부모 노드가 자식노드보다 큰 값을 가져야한다.
  • 채워진 노드 위치에서 부모 노드보다 값이 클 경우 부모 노드와 위치를 바꿔준다. (계속해서 큰 값을 가진다면 루트노드로 갈때까지 위치를 바꾼다.)
  데이터 삭제
• 보통 삭제는 루트 노드를 삭제하는 것이 일반적이다.
  • 보통은 최소값/최대값 을 알기 위해서 힙을 사용하기 때문에 루트 노드를 삭제하는것이 일반적이다.
• 루트 노드가 삭제될시에, 남아있는 데이터의 오른쪽의 끝에 존재하는 노트를 루트 노드로 위치를 변경하고 자식노드와 값을 비교해서 다시 루트노드에 최소/최대값을 배치한다.

힙과 배열

• 힙에서는 보통 데이터를 배열에 저장한다.
  • 계산을 통해서 자식 노드와 부모 노드를 찾아낸다.
• 배열은 보통 인덱스가 0부터 시작하지만, 힙을 구현할때는 0번은 null로 만든 후 1번 인덱스부터 루트 노드의 값을 저장한다.
  • 부모노드와 자식 노드는 인덱스 번호만 계산 할 수 있으면 된다.
    • 자식노드의 인덱스 번호를 2로 나눈 몫을 부모 노드의 인덱스 번호로 사용한다.
    • 왼쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 값을 사용한다.
    • 오른쪽 자식 노드의 인덱스 번호는 부모 노드의 인덱스 번호에 2를 곱한 후 1을 더한 값이 사용된다.

마무리  🤔

• 우선순위 큐를 사용할때 힙과 기존 이진탐색 트리의 차이점을 설명 못했었는데, 이제 좀 설명을 할 수 있을것 같습니다.
  • 최대힙 같은 경우에는 자식노드가 부모노드보다 값이 작거나 같아야 합니다.
  • 이진 탐색 트리같은 경우에는 검색을 위한 자료구조이고, 완전 이진트리는 최소값 최대값 을 구하기 위한 자료구조라는것을 알게되었습니다.