Python의 바이너리 힙에 대한 자세한 소개(코드 예)

이 글은 Python의 바이너리 힙에 대한 자세한 소개(코드 예제)를 제공합니다. 이는 특정 참조 값을 가지고 있습니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

1. 힙

데이터 구조 힙은 우선순위 큐입니다. 큐는 선입선출 방식의 데이터 구조입니다. 대기열의 중요한 변형을 우선순위 대기열이라고 합니다. 우선순위 큐를 사용하면 어떤 순서로든 개체를 추가할 수 있으며 언제든지(객체를 추가하는 동안) 가장 작은 요소를 찾거나 제거할 수 있습니다. 이는 Python의 min 메서드보다 더 효율적이라는 의미입니다.
우선순위 대기열에서 대기열에 있는 항목의 논리적 순서는 우선순위에 따라 결정됩니다. 우선순위가 가장 높은 항목은 대기열 앞에 있고 우선순위가 가장 낮은 항목은 대기열 뒤에 있습니다. 따라서 항목을 우선 순위 대기열에 추가하면 새 항목이 계속 앞으로 이동할 수 있습니다.

2. 바이너리 힙 작업

바이너리 힙 구현의 기본 작업은 다음과 같습니다.

BinaryHeap()은 새로운 빈 바이너리 힙을 생성합니다.
insert(k)는 힙에 새 항목을 추가합니다.
findMin()은 가장 작은 키 값을 가진 항목을 반환하고 해당 항목을 힙에 남겨 둡니다.
delMin() 가장 작은 키 값을 가진 항목을 반환하고 힙에서 해당 항목을 제거합니다.
힙이 비어 있으면 isEmpty()는 true를 반환하고, 그렇지 않으면 false를 반환합니다.
size()는 힙에 있는 항목 수를 반환합니다.
buildHeap(list) 키 목록에서 새 힙을 빌드합니다.

힙에 항목을 추가하는 순서에 관계없이 매번 가장 작은 항목이 제거됩니다.

힙이 효율적으로 작동하도록 하기 위해 이진 트리의 로그 특성을 활용하여 힙을 나타냅니다. 로그 성능을 보장하려면 트리 균형을 유지해야 합니다. 균형 이진 트리는 루트의 왼쪽과 오른쪽 하위 트리에 있는 노드 수가 거의 같고, 빈 트리이거나 왼쪽과 오른쪽 하위 트리의 높이 차이의 절대값이 1을 초과하지 않으며, 두 트리 모두 왼쪽 및 오른쪽 하위 트리는 균형 잡힌 이진 트리입니다. 힙 구현에서는 완전한 이진 트리를 생성하여 트리 균형을 유지합니다. 완전 이진 트리는 각 수준의 노드가 완전히 채워져 있는 트리이며, 마지막 수준이 가득 차지 않으면 오른쪽의 일부 노드만 누락되는 트리입니다. 그림 1은 완전한 이진 트리의 예를 보여줍니다.
완전 이진 트리의 또 다른 흥미로운 속성은 단일 목록을 사용하여 표현할 수 있다는 것입니다.

# from pythonds.trees.binheap import BinHeap
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    def insert(self,k):
        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def buildHeap(self, alist):
        '''直接将整个列表生成堆，将总开销控制在O(n)'''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本
        while (i > 0):
            self.percDown(i)
           i = i - 1
    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
    def percDown(self, i):
        &#39;&#39;&#39;将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。&#39;&#39;&#39;
        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):
        &#39;&#39;&#39;在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。&#39;&#39;&#39;
        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):
        &#39;&#39;&#39;移走根节点的元素（最小项）后如何保持堆结构和堆次序&#39;&#39;&#39;
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

바이너리 힙에 대한 마지막 부분은 정렬되지 않은 목록에서 "힙"을 생성하는 방법을 찾는 것입니다. 우리가 가장 먼저 생각하는 것은 순서가 지정되지 않은 목록의 각 요소를 차례로 힙에 삽입하는 것입니다. 정렬된 목록의 경우 이진 검색을 사용하여 적절한 위치를 찾은 다음 O(logn)의 시간 복잡도로 키 값을 다음 위치의 힙에 삽입할 수 있습니다. 또한 목록에 요소를 삽입하려면 목록의 다른 요소를 이동하여 새 노드를 위한 공간을 확보해야 하며 시간 복잡도는 O(n)입니다. 따라서 insert 메소드를 사용하는 데 드는 총 비용은 O(nlogn)입니다. 실제로 전체 목록을 힙으로 직접 생성하고 총 오버헤드를 O(n)으로 제어할 수 있습니다. Listing 6에서는 힙을 생성하는 작업을 보여줍니다.

O(n) 오버헤드로 바이너리 힙을 생성할 수 있다는 것이 다소 믿기지 않으므로 여기서는 증명하지 않겠습니다. 그러나 O(n) 오버헤드로 힙이 생성될 수 있다는 것을 이해하는 열쇠는 logn 인수가 트리의 높이를 기반으로 하기 때문입니다. buildHeap의 많은 작업에서 트리의 높이는 logn보다 작습니다.

위 내용은 Python의 바이너리 힙에 대한 자세한 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!