백엔드 개발 파이썬 튜토리얼 Python에서 바이너리 힙을 구현하는 방법

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

Mar 13, 2017 pm 06:10 PM
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)

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

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은 완전한 이진 트리를 보여줍니다.

Python에서 바이너리 힙을 구현하는 방법그림 1: 완전 이진 트리

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

색인화되면 상위 노드도

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

힙 순서 속성

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

Python에서 바이너리 힙을 구현하는 방법그림 2: 완전한 트리 및 해당 목록 표현

바이너리 힙 작업 구현

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

Listing 1


class BinHeap:
  def init(self):
    self.heapList = [0]
    self.currentSize = 0
로그인 후 복사

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

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

图 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 所示的是一系列交换操作来使新节点“下沉”到正确的位置。

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

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

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

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
로그인 후 복사

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

图 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

PHP와 Python : 다른 패러다임이 설명되었습니다 PHP와 Python : 다른 패러다임이 설명되었습니다 Apr 18, 2025 am 12:26 AM

PHP는 주로 절차 적 프로그래밍이지만 객체 지향 프로그래밍 (OOP)도 지원합니다. Python은 OOP, 기능 및 절차 프로그래밍을 포함한 다양한 패러다임을 지원합니다. PHP는 웹 개발에 적합하며 Python은 데이터 분석 및 기계 학습과 같은 다양한 응용 프로그램에 적합합니다.

PHP와 Python 중에서 선택 : 가이드 PHP와 Python 중에서 선택 : 가이드 Apr 18, 2025 am 12:24 AM

PHP는 웹 개발 및 빠른 프로토 타이핑에 적합하며 Python은 데이터 과학 및 기계 학습에 적합합니다. 1.PHP는 간단한 구문과 함께 동적 웹 개발에 사용되며 빠른 개발에 적합합니다. 2. Python은 간결한 구문을 가지고 있으며 여러 분야에 적합하며 강력한 라이브러리 생태계가 있습니다.

Python vs. JavaScript : 학습 곡선 및 사용 편의성 Python vs. JavaScript : 학습 곡선 및 사용 편의성 Apr 16, 2025 am 12:12 AM

Python은 부드러운 학습 곡선과 간결한 구문으로 초보자에게 더 적합합니다. JavaScript는 가파른 학습 곡선과 유연한 구문으로 프론트 엔드 개발에 적합합니다. 1. Python Syntax는 직관적이며 데이터 과학 및 백엔드 개발에 적합합니다. 2. JavaScript는 유연하며 프론트 엔드 및 서버 측 프로그래밍에서 널리 사용됩니다.

Python에서 비주얼 스튜디오 코드를 사용할 수 있습니다 Python에서 비주얼 스튜디오 코드를 사용할 수 있습니다 Apr 15, 2025 pm 08:18 PM

VS 코드는 파이썬을 작성하는 데 사용될 수 있으며 파이썬 애플리케이션을 개발하기에 이상적인 도구가되는 많은 기능을 제공합니다. 사용자는 다음을 수행 할 수 있습니다. Python 확장 기능을 설치하여 코드 완료, 구문 강조 및 디버깅과 같은 기능을 얻습니다. 디버거를 사용하여 코드를 단계별로 추적하고 오류를 찾아 수정하십시오. 버전 제어를 위해 git을 통합합니다. 코드 서식 도구를 사용하여 코드 일관성을 유지하십시오. 라인 도구를 사용하여 잠재적 인 문제를 미리 발견하십시오.

VScode 확장자가 악의적입니까? VScode 확장자가 악의적입니까? Apr 15, 2025 pm 07:57 PM

VS 코드 확장은 악의적 인 코드 숨기기, 취약성 악용 및 합법적 인 확장으로 자위하는 등 악성 위험을 초래합니다. 악의적 인 확장을 식별하는 방법에는 게시자 확인, 주석 읽기, 코드 확인 및주의해서 설치가 포함됩니다. 보안 조치에는 보안 인식, 좋은 습관, 정기적 인 업데이트 및 바이러스 백신 소프트웨어도 포함됩니다.

PHP와 Python : 그들의 역사에 깊은 다이빙 PHP와 Python : 그들의 역사에 깊은 다이빙 Apr 18, 2025 am 12:25 AM

PHP는 1994 년에 시작되었으며 Rasmuslerdorf에 의해 개발되었습니다. 원래 웹 사이트 방문자를 추적하는 데 사용되었으며 점차 서버 측 스크립팅 언어로 진화했으며 웹 개발에 널리 사용되었습니다. Python은 1980 년대 후반 Guidovan Rossum에 의해 개발되었으며 1991 년에 처음 출시되었습니다. 코드 가독성과 단순성을 강조하며 과학 컴퓨팅, 데이터 분석 및 기타 분야에 적합합니다.

Windows 8에서 코드를 실행할 수 있습니다 Windows 8에서 코드를 실행할 수 있습니다 Apr 15, 2025 pm 07:24 PM

VS 코드는 Windows 8에서 실행될 수 있지만 경험은 크지 않을 수 있습니다. 먼저 시스템이 최신 패치로 업데이트되었는지 확인한 다음 시스템 아키텍처와 일치하는 VS 코드 설치 패키지를 다운로드하여 프롬프트대로 설치하십시오. 설치 후 일부 확장은 Windows 8과 호환되지 않을 수 있으며 대체 확장을 찾거나 가상 시스템에서 새로운 Windows 시스템을 사용해야합니다. 필요한 연장을 설치하여 제대로 작동하는지 확인하십시오. Windows 8에서는 VS 코드가 가능하지만 더 나은 개발 경험과 보안을 위해 새로운 Windows 시스템으로 업그레이드하는 것이 좋습니다.

터미널 VSCODE에서 프로그램을 실행하는 방법 터미널 VSCODE에서 프로그램을 실행하는 방법 Apr 15, 2025 pm 06:42 PM

vs 코드에서는 다음 단계를 통해 터미널에서 프로그램을 실행할 수 있습니다. 코드를 준비하고 통합 터미널을 열어 코드 디렉토리가 터미널 작업 디렉토리와 일치하는지 확인하십시오. 프로그래밍 언어 (예 : Python의 Python Your_file_name.py)에 따라 실행 명령을 선택하여 성공적으로 실행되는지 여부를 확인하고 오류를 해결하십시오. 디버거를 사용하여 디버깅 효율을 향상시킵니다.

See all articles