为什么heapify将堆的顶部与底部的元素交换？ [英] Why does heapify swap the top of the heap with the element at the bottom of the heap?

问题描述

在最大堆中（假设它由数组表示），堆的顶部（即堆中的最大值）与数组中的最后一个元素（即堆中的最小值之一）交换），最后一个元素将被删除，然后新的top-of-theap元素将与其他值交换以重新放置在其适当位置。

In a max heap (assuming it's represented by an array), the top of the heap (ie. the largest value in the heap) swaps with the last element in the array (ie. one of the smallest values in the heap), the last element is removed, and then the new top-of-the-heap element swaps with other values to settle back into its proper place.

相反，为什么不删除顶部元素，然后其他元素可以填充堆呢？

Instead, why isn't the top element just removed and then other elements can "fill in" for the the heap?

推荐答案

堆的关键属性之一是底层的二叉树是一棵 complete 二叉树（即除最后一层外的每一层都有完全填充）。这样一来，堆就具有 O（lg N）操作，因为我们只需要在每个 O（lg N）级。让我们看一个例子

One of the key properties of a heap is that the underlying binary tree is a complete binary tree (i.e. every level except the last one has to be completely "filled"). This is so that the heap has O(lg N) operations because we only have to modify one element at each of the O(lg N) levels. Let's take a look at an example

    10
   /  \
  8    7
 / \  / \
5  6  4  3

如果我们遵循您的方法并填写在我们得到的堆中

If we follow your method and "fill in" the heap we get

     8
   /   \
  6     7
 / \   / \
5  ?   4  3

树不再是完整的二叉树，因为？。由于我们不知道树是完整的，所以我们对树的高度一无所知，因此我们不能保证 O（lg N）操作。

The tree is no longer a complete binary tree as there is a "hole" at the ?. Since we don't know that the tree is complete, we don't know anything about the height of the tree and so we can't guarantee O(lg N) operations.

这就是为什么我们将堆中的最后一个元素放在顶部，然后将其重新排列以保持完整的二叉树属性。

This is why we take the last element in the heap, put it on top and then shuffle it down - to maintain the complete binary tree property.

这篇关于为什么heapify将堆的顶部与底部的元素交换？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！