二叉堆的陣列表示

遵循堆排序屬性的完全二叉樹稱為**二叉堆**。

根據二叉堆的排序，它可以分為兩種型別：

**最小堆**是指節點的值大於或等於其父節點值的堆。最小堆的根節點值最小。

**最大堆**是指節點的值小於或等於其父節點值的堆。最大堆的根節點值最大。

二叉堆的值通常表示為**陣列**。二叉堆的陣列表示如下：

• 根元素的索引為0。

• 如果i是陣列中節點的索引，則與該節點相關的其他節點在陣列中的索引為：

  • 左孩子：(2*i)+1

  • 右孩子：(2*i)+2

  • 父節點：(i-1)/2

使用上述陣列表示規則，我們可以用陣列表示堆：

現在，我們可以討論基於排序型別的堆：

• **最小堆** - 根節點具有最小值。節點的值大於父節點的值。

示例：

陣列表示：

• **最大堆** - 根節點具有最大值。節點的值小於父節點的值。

示例：

陣列表示：

作者：sudhir sharma

更新於：2019年11月13日

3K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習