Python에서 바이너리 힙을 구현하는 방법

이진 힙은 특별한 종류의 힙입니다. 이진 힙은 완전한 이진 트리(이진 트리) 또는 대략 완전한 이진 트리(이진 트리)입니다. 바이너리 힙에는 최대 힙과 최소 힙의 두 가지 유형이 있습니다. 최대 힙: 상위 노드의 키 값은 항상 하위 노드의 키 값보다 크거나 같습니다. 최소 힙: 상위 노드의 키 값은 항상 하위 노드의 키 값보다 작거나 같습니다.

우선순위 큐의 바이너리 힙 구현

이전 장에서 "선입 선출"(FIFO)의 데이터 구조를 배웠습니다. 🎜>). "우선순위 대기열"(Queue)이라는 대기열 변형이 있습니다. 우선순위 큐의 dequeue(Priority Queue) 동작은 큐와 동일하며, 큐의 선두부터 dequeue된다. 그러나 우선순위 큐 내에서 요소의 순서는 "Dequeue우선순위"에 의해 결정됩니다. 우선순위가 높은 요소는 큐의 맨 앞에 순위가 매겨지고, 우선순위가 낮은 요소는 맨 뒤에 순위가 매겨집니다. 이런 식으로 우선순위 큐의 엔큐잉() 작업은 더 복잡해지고, 우선순위에 따라 요소를 최대한 큐에 넣어야 합니다. 다음 섹션에서는 우선순위 큐가 그래프 알고리즘에 유용한 데이터 구조라는 것을 알게 될 것입니다. Enqueue

우리는 우선순위 대기열을 구현하기 위해 정렬 알고리즘과 대기열을 사용하는 것을 자연스럽게 생각합니다. 그러나 목록에 요소를 삽입하는 시간 복잡도는

이고, 목록을 정렬하는 시간 복잡도는 O(n)입니다. 시간 복잡성을 줄이기 위해 다른 방법을 사용할 수 있습니다. 우선순위 큐를 구현하는 전형적인 방법은 바이너리 힙(O(nlogn))을 사용하는 것입니다. 바이너리 힙은 Binary Heap에서 우선순위 큐의 대기열 추가 및 대기열 제거의 복잡성을 유지할 수 있습니다. O(logn)

바이너리 힙의 흥미로운 점은 논리적 구조가 이진 트리와 비슷하지만 중첩되지 않은 목록으로 구현된다는 것입니다. 바이너리 힙에는 두 가지 유형이 있습니다. 가장 작은 키 값을 가진 힙은 항상 대기열의 헤드에 배치되며, 반대로 가장 큰 키 값을 가진 힙은 항상 큐의 헤드에 배치됩니다. 큐의 "최대 힙(

) )"이라고 합니다. 이 섹션에서는 최소 힙을 사용합니다. min heapmax heap

바이너리 힙 작업

바이너리 힙의 기본 작업은 다음과 같이 정의됩니다.

1. : 생성 빈 바이너리 힙 객체

   BinaryHeap()

2. : 힙에 새 요소 추가

   insert(k)

3. : 힙에서 가장 작은 요소 반환 항목, 최소 항목이 힙에 남아 있음

   findMin()

4. : 힙에서 최소 항목을 제거하는 동시에 힙에 있는 최소 항목을 반환합니다.

   delMin()

5. : 힙이 비어 있는지 여부를 반환

   isEmpty()

6. : 힙에 있는 노드 수를 반환

   size()

7. : 포함된 노드 목록에서 새 힙 생성

   buildHeap(list)

아래 표시된 코드는 바이너리 힙의 예입니다. 힙에 요소를 추가하는 순서에 관계없이 매번 가장 작은 요소가 제거된다는 것을 알 수 있습니다. 다음에 이 프로세스를 구현하겠습니다.

from pythonds.trees.binheap import BinHeap

bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

힙을 더 잘 구현하기 위해 이진 트리를 사용합니다. 우리는 항상 이진 트리의 "균형"을 유지해야 하며, 항상 로그 척도에서 작업을 유지해야 합니다. 균형 이진 트리는 루트 노드의 왼쪽 하위 트리와 오른쪽 하위 트리에 동일한 수의 하위 노드가 있습니다. 힙 구현에서는 "균형"을 대략적으로 달성하기 위해 "완전한 이진 트리" 구조를 사용합니다. 완전한 이진 트리는 각 내부 노드 트리가 최대값에 도달한다는 것을 의미합니다. 단, 마지막 레벨에는 오른쪽에 있는 여러 노드만 부족할 수 있습니다. 그림 1은 완전한 이진 트리를 보여줍니다.

그림 1: 완전 이진 트리

흥미롭게도 단일 목록으로 완전한 트리를 얻을 수 있습니다. 노드, 참조 또는 중첩 목록을 사용할 필요가 없습니다. 완전한 이진 트리의 경우 목록에 있는 노드의 첨자가 p이면 왼쪽 자식 노드의 첨자는 2p이고 오른쪽 노드는 2p+1입니다. 어떤 노드의 상위 노드를 찾으려면 Python의 정수 나누기를 직접 사용할 수 있습니다. 목록에서 노드가

색인화되면 상위 노드도

색인화됩니다. 그림 2는 완전한 이진 트리와 트리의 목록 표현을 보여줍니다. 상위 노드와 하위 노드 간의 2p 및 2p+1 관계에 유의하십시오. 완전한 트리의 목록 표현은 완전한 이진 트리의 속성을 결합하므로 간단한 수학적 방법을 사용하여 전체 트리를 효율적으로 탐색할 수 있습니다. 또한 이를 통해 바이너리 힙을 효율적으로 구현할 수 있습니다. nn//2

힙 순서 속성

힙에 요소를 저장하는 방법은 힙의 순서에 따라 다릅니다. 소위 힙 순서는 힙에 있는 임의의 노드 x에 대해 해당 상위 노드 p의 키 값이 x의 키 값보다 작거나 같다는 것을 의미합니다. 그림 2는 힙 순서 속성이 있는 완전한 이진 트리를 보여줍니다.

그림 2: 완전한 트리 및 해당 목록 표현

바이너리 힙 작업 구현

接下来我们来构造二叉堆。因为可以采用一个列表保存堆的数据，构造函数只需要初始化一个列表和一个currentSize来表示堆当前的大小。Listing 1 所示的是构造二叉堆的 python 代码。注意到二叉堆的heaplist并没有用到，但为了后面代码可以方便地使用整除，我们仍然保留它。

Listing 1

class BinHeap:
  def init(self):
    self.heapList = [0]
    self.currentSize = 0

我们接下来要实现的是insert方法。首先，为了满足“完全二叉树”的性质，新键值应该添加到列表的末尾。然而新键值简单地添加在列表末尾，显然无法满足堆次序。但我们可以通过比较父节点和新加入的元素的方法来重新满足堆次序。如果新加入的元素比父节点要小，可以与父节点互换位置。图 3 所示的是一系列交换操作来使新加入元素“上浮”到正确的位置。

图 3：新节点“上浮”到其正确位置

当我们让一个元素“上浮”时，我们要保证新节点与父节点以及其他兄弟节点之间的堆次序。当然，如果新节点非常小，我们仍然需要将它交换到其他层。事实上，我们需要不断交换，直到到达树的顶端。Listing 2 所示的是“上浮”方法，它把一个新节点“上浮”到其正确位置来满足堆次序。这里很好地体现了我们之前在headlist中没有用到的元素 0 的重要性。这样只需要做简单的整除，将当前节点的下标除以 2，我们就能计算出任何节点的父节点。

在Listing 3 中，我们已经可以写出insert方法的代码。insert里面很大一部分工作是由percUp函数完成的。当树添加新节点时，调用percUp就可以将新节点放到正确的位置上。

Listing 2

def percUp(self,i):
  while i // 2 > 0:
   if self.heapList[i] < self.heapList[i // 2]:
     tmp = self.heapList[i // 2]
     self.heapList[i // 2] = self.heapList[i]
     self.heapList[i] = tmp
   i = i // 2

Listing 3

def insert(self,k):
  self.heapList.append(k)
  self.currentSize = self.currentSize + 1
  self.percUp(self.currentSize)

我们已经写好了insert方法，那再来看看delMin方法。堆次序要求根节点是树中最小的元素，因此很容易找到最小项。比较困难的是移走根节点的元素后如何保持堆结构和堆次序，我们可以分两步走。首先，用最后一个节点来代替根节点。移走最后一个节点保持了堆结构的性质。这么简单的替换，还是会破坏堆次序。那么第二步，将新节点“下沉”来恢复堆次序。图 4 所示的是一系列交换操作来使新节点“下沉”到正确的位置。

图 4：替换后的根节点下沉

为了保持堆次序，我们需将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。Listing 4 所示的是新节点下沉所需的percDown和minChild方法的代码。

Listing 4

def percDown(self,i):
  while (i * 2) <= self.currentSize:
    mc = self.minChild(i)
    if self.heapList[i] > self.heapList[mc]:
      tmp = self.heapList[i]
      self.heapList[i] = self.heapList[mc]
      self.heapList[mc] = tmp
    i = mc

def minChild(self,i):
  if i * 2 + 1 > self.currentSize:
    return i * 2
  else:
    if self.heapList[i*2] < self.heapList[i*2+1]:
      return i * 2
    else:
      return i * 2 + 1

Listing 5 所示的是delMin操作的代码。可以看到比较麻烦的地方由一个辅助函数来处理，即percDown。

Listing 5

def delMin(self):
  retval = self.heapList[1]
  self.heapList[1] = self.heapList[self.currentSize]
  self.currentSize = self.currentSize - 1
  self.heapList.pop()
  self.percDown(1)
  return retval

关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是，将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表，我们可以用二分搜索找到合适的位置，然后在下一个位置插入这个键值到堆中，时间复杂度为O(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动，为新节点腾出位置，时间复杂度为O(n)。因此用insert方法的总开销是O(nlogn)。其实我们能直接将整个列表生成堆，将总开销控制在O(n)。Listing 6 所示的是生成堆的操作。

Listing 6

def buildHeap(self,alist):
  i = len(alist) // 2
  self.currentSize = len(alist)
  self.heapList = [0] + alist[:]
  while (i > 0):
    self.percDown(i)
    i = i - 1

图 5：将列表[ 9, 6, 5, 2, 3]生成一个二叉堆

图 5 所示的是利用buildHeap方法将最开始的树[ 9, 6, 5, 2, 3]中的节点移动到正确的位置时所做的交换操作。尽管我们从树中间开始，然后回溯到根节点，但percDown方法保证了最大子节点总是“下沉”。因为堆是完全二叉树，任何在中间的节点都是叶节点，因此没有子节点。注意，当i=1时，我们从根节点开始下沉，这就需要进行大量的交换操作。可以看到，图 5 最右边的两颗树，首先 9 从根节点的位置移走，移到下一层级之后，percDown进一步检查它此时的子节点，保证它下降到不能再下降为止，即下降到正确的位置。然后进行第二次交换，9 和 3 的交换。由于 9 已经移到了树最底层的层级，便无法进一步交换了。比较一下列表表示法和图 5 所示的树表示法进行的一系列交换还是很有帮助的。

i = 2 [0, 9, 5, 6, 2, 3]
i = 1 [0, 9, 2, 6, 5, 3]
i = 0 [0, 2, 3, 6, 5, 9]

下列所示的代码是完全二叉堆的实现。

def insert(self,k):
   self.heapList.append(k)
   self.currentSize = self.currentSize + 1
   self.percUp(self.currentSize)

  def percDown(self,i):
   while (i * 2) <= self.currentSize:
     mc = self.minChild(i)
     if self.heapList[i] > self.heapList[mc]:
       tmp = self.heapList[i]
       self.heapList[i] = self.heapList[mc]
       self.heapList[mc] = tmp
     i = mc

  def minChild(self,i):
   if i * 2 + 1 > self.currentSize:
     return i * 2
   else:
     if self.heapList[i*2] < self.heapList[i*2+1]:
       return i * 2
     else:
       return i * 2 + 1

  def delMin(self):
   retval = self.heapList[1]
   self.heapList[1] = self.heapList[self.currentSize]
   self.currentSize = self.currentSize - 1

能在O(n)的开销下能生成二叉堆看起来有点不可思议，其证明超出了本书的范围。但是，要理解用O(n)的开销能生成堆的关键是因为logn因子基于树的高度。而对于buildHeap里的许多操作，树的高度比logn要小。

위 내용은 Python에서 바이너리 힙을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!