ホームページ バックエンド開発 Python チュートリアル Python でバイナリ ヒープを実装する方法

Python でバイナリ ヒープを実装する方法

Mar 13, 2017 pm 06:10 PM
python バイナリヒープ

バイナリ ヒープは特別な種類のヒープです。バイナリ ヒープは、完全なバイナリ ツリー (バイナリ ツリー)、またはほぼ完全なバイナリ ツリー (バイナリ ツリー) です。バイナリ ヒープには、max-heap と min-heap の 2 種類があります。最大ヒープ: 親ノードのキー値は常に​​子ノードのキー値以上です。最小ヒープ: 親ノードのキー値は常に​​子ノードのキー値以下です。

優先キューのバイナリヒープ実装

前の章では、「先入れ先出し」 (FIFO) のデータ構造を学習しました。 >)。 「Priority Queue」(Priority Queue) と呼ばれるキューのバリエーションがあります。優先キューのデキュー (Dequeue) 操作はキューと同じで、キューの先頭からデキューされます。ただし、優先キュー内では、要素の順序は「優先度」によって決定されます: 高-優先度の高い要素はキューの先頭に並べ替えられ、優先度の低い要素は最後に並べ替えられます。このように、優先度キューのエンキュー (Enqueue) 操作はより複雑になり、要素は優先度に従って可能な限りキューに入れられる必要があります。次のセクションでは、優先キューがグラフ アルゴリズムにとって有用なデータ構造であることがわかります。 FIFO)的数据结构:队列(Queue)。队列有一种变体叫做“优先队列”(Priority Queue)。优先队列的出队(Dequeue)操作和队列一样,都是从队首出队。但在优先队列的内部,元素的次序却是由“优先级”来决定:高优先级的元素排在队首,而低优先级的元素则排在后面。这样,优先队列的入队(Enqueue)操作就比较复杂,需要将元素根据优先级尽量排到队列前面。我们将会发现,对于下一节要学的图算法中的优先队列是很有用的数据结构。

我们很自然地会想到用排序算法和队列的方法来实现优先队列。但是,在列表里插入一个元素的时间复杂度是O(n),对列表进行排序的时间复杂度是O(nlogn)。我们可以用别的方法来降低时间复杂度。一个实现优先队列的经典方法便是采用二叉堆(Binary Heap)。二叉堆能将优先队列的入队和出队复杂度都保持在O(logn)

二叉堆的有趣之处在于,其逻辑结构上像二叉树,却是用非嵌套的列表来实现。二叉堆有两种:键值总是最小的排在队首称为“最小堆(min heap)”,反之,键值总是最大的排在队首称为“最大堆(max 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 所示是一个完全二叉树。

Python でバイナリ ヒープを実装する方法

图 1:完全二叉树

有意思的是我们用单个列表就能实现完全树。我们不需要使用节点,引用或嵌套列表。因为对于完全二叉树,如果节点在列表中的下标为 p,那么其左子节点下标为 2p,右节点为 2p+1。当我们要找任何节点的父节点时,可以直接使用 python 的整除。如果节点在列表中下标为n,那么父节点下标为n//2

優先キューを実装するには、ソートアルゴリズムとキューを使用することを当然考えます。ただし、リストへの要素の挿入の時間計算量は O(n) であり、リストの並べ替えの時間計算量は O(nlogn) です。他の方法を使用して、時間の複雑さを軽減できます。優先キューを実装する古典的な方法は、バイナリ ヒープ (Binary Heap) を使用することです。バイナリ ヒープは、優先キューのエンキューとデキューの両方の複雑さを O(logn) に保つことができます。

バイナリ ヒープの興味深い点は、その論理構造はバイナリ ツリーに似ていますが、ネストされていないリストで実装されていることです。バイナリ ヒープには 2 つのタイプがあります。最小のキー値が常にキューの先頭にあるものは「最小ヒープ (min heap)」と呼ばれ、逆に、最大のキー値が常にキューの先頭にあります。キューの先頭の値は「最小ヒープ (max heap)」と呼ばれます。このセクションでは、min-heap を使用します。

バイナリヒープの操作

Python でバイナリ ヒープを実装する方法バイナリヒープの基本的な操作定義は次のとおりです:

  1. BinaryHeap(): Create空のバイナリ ヒープ オブジェクト

  2. insert(k): ヒープに新しい要素を追加します

  3. findMin()</code >: ヒープ内の最小の項目を返し、その最小の項目はヒープに残ります</p></li><li>🎜<code>delMin(): ヒープ内の最小の項目を返し、ヒープから削除しますheap 🎜
  4. 🎜isEmpty(): ヒープが空かどうかを返します🎜
  5. 🎜size(): サイズを返しますヒープ内のノードの番号🎜
  6. 🎜buildHeap(list): ノードを含むリストから新しいヒープを作成します🎜
🎜示されているコード以下はバイナリのヒープの例です。どの順序で要素をヒープに追加しても、毎回最小の要素が削除されることがわかります。次にこの処理を実装していきます。 🎜


🎜

class BinHeap:
  def init(self):
    self.heapList = [0]
    self.currentSize = 0
ログイン後にコピー
ログイン後にコピー
🎜 ヒープをより適切に実装するために、バイナリ ツリーを使用します。二分木の「バランス」を常に維持し、常に対数スケールでの操作を維持する必要があります。バランスの取れたバイナリ ツリーには、ルート ノードの左右のサブツリーに同じ数の子ノードがあります。ヒープの実装では、「完全なバイナリ ツリー」の構造を使用して、ほぼ「バランス」を実現します。完全なバイナリ ツリーとは、各内部ノード ツリーがその最大値に達することを意味します。ただし、最後のレベルには右側のいくつかのノードしか欠けることはありません。図 1 は、完全なバイナリ ツリーを示しています。 🎜🎜バイナリ ヒープを実装する Python メソッド🎜🎜図 1: 完全なバイナリ ツリー🎜🎜興味深いことに、単一のリストで完全なツリーを実装できます。ノード、参照、またはネストされたリストを使用する必要はありません。完全な二分木の場合、リスト内のノードの添え字が p の場合、その左側の子ノードの添え字は 2p で、右側のノードの添え字は 2p+1 となるためです。任意のノードの親ノードを見つけたい場合は、Python の整数除算を直接使用できます。リスト内でノードのインデックスが n である場合、親ノードのインデックスは n//2 になります。図 2 は、完全なバイナリ ツリーとツリーのリスト表現を示しています。親ノードと子ノード間の 2p および 2p+1 関係に注目してください。完全なツリーのリスト表現は完全なバイナリ ツリーのプロパティを組み合わせているため、単純な数学的手法を使用して完全なツリーを効率的に走査することができます。これにより、バイナリ ヒープを効率的に実装することもできます。 🎜🎜🎜ヒープ順序のプロパティ🎜🎜🎜 ヒープに要素を格納する方法は、ヒープの順序によって異なります。いわゆるヒープ順序は、ヒープ内の任意のノード 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 所示的是一系列交换操作来使新加入元素“上浮”到正确的位置。

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 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、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

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

PHPおよびPython:さまざまなパラダイムが説明されています PHPおよびPython:さまざまなパラダイムが説明されています Apr 18, 2025 am 12:26 AM

PHPは主に手順プログラミングですが、オブジェクト指向プログラミング(OOP)もサポートしています。 Pythonは、OOP、機能、手続き上のプログラミングなど、さまざまなパラダイムをサポートしています。 PHPはWeb開発に適しており、Pythonはデータ分析や機械学習などのさまざまなアプリケーションに適しています。

PHPとPythonの選択:ガイド PHPとPythonの選択:ガイド Apr 18, 2025 am 12:24 AM

PHPはWeb開発と迅速なプロトタイピングに適しており、Pythonはデータサイエンスと機械学習に適しています。 1.PHPは、単純な構文と迅速な開発に適した動的なWeb開発に使用されます。 2。Pythonには簡潔な構文があり、複数のフィールドに適しており、強力なライブラリエコシステムがあります。

Python vs. JavaScript:学習曲線と使いやすさ Python vs. JavaScript:学習曲線と使いやすさ Apr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

Windows 8でコードを実行できます Windows 8でコードを実行できます Apr 15, 2025 pm 07:24 PM

VSコードはWindows 8で実行できますが、エクスペリエンスは大きくない場合があります。まず、システムが最新のパッチに更新されていることを確認してから、システムアーキテクチャに一致するVSコードインストールパッケージをダウンロードして、プロンプトとしてインストールします。インストール後、一部の拡張機能はWindows 8と互換性があり、代替拡張機能を探すか、仮想マシンで新しいWindowsシステムを使用する必要があることに注意してください。必要な拡張機能をインストールして、適切に動作するかどうかを確認します。 Windows 8ではVSコードは実行可能ですが、開発エクスペリエンスとセキュリティを向上させるために、新しいWindowsシステムにアップグレードすることをお勧めします。

PHPとPython:彼らの歴史を深く掘り下げます PHPとPython:彼らの歴史を深く掘り下げます Apr 18, 2025 am 12:25 AM

PHPは1994年に発信され、Rasmuslerdorfによって開発されました。もともとはウェブサイトの訪問者を追跡するために使用され、サーバー側のスクリプト言語に徐々に進化し、Web開発で広く使用されていました。 Pythonは、1980年代後半にGuidovan Rossumによって開発され、1991年に最初にリリースされました。コードの読みやすさとシンプルさを強調し、科学的コンピューティング、データ分析、その他の分野に適しています。

ターミナルVSCODEでプログラムを実行する方法 ターミナルVSCODEでプログラムを実行する方法 Apr 15, 2025 pm 06:42 PM

VSコードでは、次の手順を通じて端末でプログラムを実行できます。コードを準備し、統合端子を開き、コードディレクトリが端末作業ディレクトリと一致していることを確認します。プログラミング言語(pythonのpython your_file_name.pyなど)に従って実行コマンドを選択して、それが正常に実行されるかどうかを確認し、エラーを解決します。デバッガーを使用して、デバッグ効率を向上させます。

VSCODE拡張機能は悪意がありますか? VSCODE拡張機能は悪意がありますか? Apr 15, 2025 pm 07:57 PM

VSコード拡張機能は、悪意のあるコードの隠れ、脆弱性の活用、合法的な拡張機能としての自慰行為など、悪意のあるリスクを引き起こします。悪意のある拡張機能を識別する方法には、パブリッシャーのチェック、コメントの読み取り、コードのチェック、およびインストールに注意してください。セキュリティ対策には、セキュリティ認識、良好な習慣、定期的な更新、ウイルス対策ソフトウェアも含まれます。

Visual StudioコードはPythonで使用できますか Visual StudioコードはPythonで使用できますか Apr 15, 2025 pm 08:18 PM

VSコードはPythonの書き込みに使用でき、Pythonアプリケーションを開発するための理想的なツールになる多くの機能を提供できます。ユーザーは以下を可能にします。Python拡張機能をインストールして、コードの完了、構文の強調表示、デバッグなどの関数を取得できます。デバッガーを使用して、コードを段階的に追跡し、エラーを見つけて修正します。バージョンコントロールのためにGitを統合します。コードフォーマットツールを使用して、コードの一貫性を維持します。糸くずツールを使用して、事前に潜在的な問題を発見します。

See all articles