Go의 최대 힙

사례here와 마찬가지로 다른 데이터 구조를 다시 방문하고 싶었습니다. 최대 힙(또는 최소 힙)은 하위 값보다 크거나 작은 노드가 있는 완전한 이진 트리인 우선 순위 큐를 만드는 데 일반적으로 사용되는 데이터 구조입니다.

이전에 구현한 BST와 달리 Max Heap은 하위 항목에 더 쉽게 액세스할 수 있도록 배열을 사용하여 일반적으로 구현했습니다. 각 노드 부모 또는 자식에 액세스하기 위해 전체 배열을 트리로 시각화할 수 있습니다. 이미지가 없으므로 다른 웹사이트에서 Max Heap 이미지를 선택합니다. 개념은 Min Heap과 동일합니다.



마지막으로 배열을 1부터 시작합니다(웃음). 왜 1부터 시작할까요? 이 수식으로 인덱스 0에 액세스할 수 없기 때문입니다.

위에 제공된 이미지를 참조하면 노드의 왼쪽 자식이 currentIndex * 2 에 있고 오른쪽 자식이 currentIndex * 2 + 1 에 있음을 시각화할 수 있으며 currentIndex / 2 를 사용하여 노드의 부모에 액세스할 수 있습니다.

예를 들어 값이 15 인 노드에는 10 및 5 인 2개의 자식이 있습니다. 15 인 3 의 인덱스를 볼 수 있습니다. 왼쪽 자식은 인덱스가 10 인 3 * 2 = 6 이고 오른쪽 자식은 인덱스가 5 인 3 * 2 + 1 = 7 입니다.

이론이 충분하면 책에서 읽을 수 있습니다. Go를 사용하여 여기에 구현을 작성하고 싶습니다. Push , Pop 및 Peek 작업만 구현합니다. 작업의 이름을 정하기는 어렵지만 작업을 설명하는 한 괜찮습니다.

MaxHeap 구조체 정의

type MaxHeap struct {
  heap []int
  capacity int
  size int
  root int
}

MaxHeap에는 최소한 크기, 용량 및 힙 자체가 있습니다. root 속성은 루트가 항상 constant 여야 하므로 1 입니다. size는 힙의 현재 크기를 정의하고, capacity는 힙이 데이터를 저장할 수 있는 양을 정의하며, heap 자체는 데이터를 저장한 배열입니다.

건설자

func NewMaxHeap(capacity int) *MaxHeap {
  // because we used the 0 index
  // we need to increase the capacity defined by user
  c := capacity + 1
  h := make([]int, c, c)

  // just to mark that it is the minimum one,
  // you can ignore this
  h[0] = (1 << 31) - 1

  return &MaxHeap{
    root: 1, // always 1, you can omit this attribute
    size: 0,
    capacity: c,
    heap: h,
  }
}

도우미 메서드

func (MaxHeap) getParent(idx int) int {
  return idx / 2
}

func (MaxHeap) getLeft(idx int) int {
  return idx * 2
}

func (MaxHeap) getRight(idx int) int {
  return idx*2 + 1
}

func (m *MaxHeap) swap(idx1, idx2 int) {
  m.heap[idx1], m.heap[idx2] = m.heap[idx2], m.heap[idx1]
}

func (m MaxHeap) String() string {
  return fmt.Sprintf(`size: %v
capacity: %v
heap: %v`,
    m.size, m.capacity-1, m.heap[1:])
}

푸시

최대/최소 힙으로 밀어넣는 것은 쉬워야 합니다. 인덱스에 따라 요소를 배치하고 해당 값이 부모보다 큰지/작은지 확인하고, 최대 힙을 구현하는 경우 해당 값이 다음보다 큰지 확인하십시오. 부모인 경우 해당 값을 부모 값으로 바꿉니다.

func (m *MaxHeap) Push(element int) {
  // check whether it can store the element
  if m.size >= m.capacity-1 {
    return
  }

  m.size++
  idx := m.size

  // put it according to the index
  m.heap[idx] = element

  parent := m.getParent(idx)

  // check if its value is greater than its parent
  for m.heap[idx] > m.heap[parent] {
    // then swap
    m.swap(idx, parent)

    // repeat the process until
    // the greatest value is on the top
    idx = parent
    parent = m.getParent(idx)
  }
}

몰래 엿보다

Peek 작업은 루트인 최대/최소 값을 반환합니다.

func (m MaxHeap) Peek() (int, error) {
  if m.size <= 0 {
    return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty")
  }

  return m.heap[m.root], nil
}

우리의 힙을 확인하자

func main() {
  h := NewMaxHeap(15)
  h.Push(1)
  h.Push(4)
  h.Push(2)
  h.Push(5)

  fmt.Println(h)
  g, _ := h.Peek()
  fmt.Println("greatest:", g)
}

출력은 다음과 같아야 합니다.

size: 4
capacity: 15
heap: [5 4 2 1 0 0 0 0 0 0 0 0 0 0 0]
greatest: 5

팝

이제 무언가를 터뜨려 봅시다. 팝핑 작업은 가장 큰 값/최소한 값을 반환하고 힙에서 삭제합니다. 힙의 균형을 재조정해야 합니다. 따라서 가장 큰/최소한 값이 다시 루트가 됩니다.

func (m *MaxHeap) rebalance(idx int) {
  // don't rebalance if node index
  // is greater than heap size
  if idx >= m.size {
    return
  }

  // fetch the left child index
  left := m.getLeft(idx)

  // fetch the right child index
  right := m.getRight(idx)

  // only swap if children position is wrong
  // and only the children index is less than heap size
  // and then rebalance it
  if left <= m.size {
    if m.heap[idx] < m.heap[left] {
      m.swap(idx, left)
      m.rebalance(left)
    }
  }

  if right <= m.size {
    if m.heap[idx] < m.heap[right] {
      m.swap(idx, right)
      m.rebalance(right)
    }
  }
}

func (m *MaxHeap) Pop() (int, error) {
  if m.size <= 0 {
    return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty")
  }

  // fetch the root
  max := m.heap[m.root]
  // make the route is the last element in the heap
  m.heap[m.root] = m.heap[m.size]
  // make it zero value
  m.heap[m.size] = 0
  // decrease the size so the zero value won't be counted
  m.size--

  // rebalance the heap
  m.rebalance(m.root)

  // return the greatest
  return max, nil
}

따라서 Pop 작업이 호출될 때마다 힙은 맨 위에서 리프까지 균형을 재조정합니다. 전체 코드는 다음과 같아야 합니다.

package main

import "fmt"

type MaxHeap struct {
  heap []int
  capacity int
  size int
  root int
}

func (MaxHeap) getParent(idx int) int {
  return idx / 2
}

func (MaxHeap) getLeft(idx int) int {
  return idx * 2
}

func (MaxHeap) getRight(idx int) int {
  return idx*2 + 1
}

func (m *MaxHeap) swap(idx1, idx2 int) {
  m.heap[idx1], m.heap[idx2] = m.heap[idx2], m.heap[idx1]
}

func (m MaxHeap) String() string {
  return fmt.Sprintf(`size: %v
capacity: %v
heap: %v`,
    m.size, m.capacity-1, m.heap[1:])
}

func (m *MaxHeap) rebalance(idx int) {
  if idx >= m.size {
    return
  }

  left := m.getLeft(idx)
  right := m.getRight(idx)

  if left <= m.size {
    if m.heap[idx] < m.heap[left] {
      m.swap(idx, left)
      m.rebalance(left)
    }
  }

  if right <= m.size {
    if m.heap[idx] < m.heap[right] {
      m.swap(idx, right)
      m.rebalance(right)
    }
  }
}

func (m *MaxHeap) Pop() (int, error) {
  if m.size <= 0 {
    return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty")
  }

  // fetch the root
  max := m.heap[m.root]
  // make the route is the last element in the heap
  m.heap[m.root] = m.heap[m.size]
  // make it zero value
  m.heap[m.size] = 0
  // decrease the size so the zero value won't be counted
  m.size--

  // rebalance the heap
  m.rebalance(m.root)

  // return the greatest
  return max, nil
}

func (m MaxHeap) Peek() (int, error) {
  if m.size <= 0 {
    return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty")
  }

  return m.heap[m.root], nil
}

func (m *MaxHeap) Push(element int) {
  // exceed the limit
  if m.size >= m.capacity-1 {
    return
  }

  m.size++
  idx := m.size

  m.heap[idx] = element

  parent := m.getParent(idx)

  for m.heap[idx] > m.heap[parent] {
    m.swap(idx, parent)

    idx = parent
    parent = m.getParent(idx)
  }
}

func NewMaxHeap(capacity int) *MaxHeap {
  // because we used the 0 index
  // we need to increase the capacity defined by user
  c := capacity + 1
  h := make([]int, c, c)

  // just to mark that it is the minimum one,
  // you can ignore this
  h[0] = (1 << 31) - 1

  return &MaxHeap{
    root: 1, // always 1, you can omit this attribute
    size: 0,
    capacity: c,
    heap: h,
  }
}

func main() {
  h := NewMaxHeap(15)
  h.Push(1)
  h.Push(4)
  h.Push(2)
  h.Push(5)
  h.Push(3)
  h.Push(10)

  fmt.Println(h.Pop())
  fmt.Println(h.Pop())
  fmt.Println(h.Pop())
  h.Push(11)

  fmt.Println(h)
}