时间戳

首页 > 解决方案 > 递归构建堆的自顶向下算法

algorithm - 递归构建堆的自顶向下算法

问题描述

我对我正在研究的问题中的自上而下的要求有点困惑。

这是一个算法问题，所以我将使用伪代码。假设我们有一个算法来对长度为 n的数组A进行排序。排序算法有一个函数buildMaxHeap在发生其他任何事情之前将数组转换为堆：

HeapSrt(A){
  A.buildMaxHeap() // turn array A into a maxheap
  for i = A.length-1 to 0
    swap(A, 0, i)
    A.siftDwn(0)
}

其中 buildMaxHeap 是一个自下而上的迭代函数：

A.buildMaxHeap(){
  for i = (n-1)/2 to 0
  A.siftDwn(i)
}

假设，我们需要把buildMaxHeap变成一个自顶向下的递归函数。我们可以假设叶子 lvl 已满（每个父元素正好有 2 个子元素）。此外，我们可以假设已经实现了筛选功能。

我的问题：

我对自上而下的要求有些困惑：我从顶部开始递归，但实际的 siftdwn 嘉豪从底部开始（一旦我们达到基本情况）。那么，它算不算自上而下的递归堆法呢？

谢谢！

标签： algorithmrecursion

解决方案

递归算法是一种自顶向下的算法。

诚然，问题仍然可以通过首先整理堆底部，然后才是堆顶部来解决，但这与自上而下的方法并不矛盾。

通常，使用递归算法解决的第一个“问题”是出现在其递归树的叶子中的问题：一旦发现可以解决的问题，它就会回溯。最后解决的问题是递归算法开始的初始问题。这是递归算法的典型特征。

自上而下算法的特点是它首先查看顶层的“大”问题，然后决定将其分解为一个或多个“更简单”的问题，然后递归处理。当这些解决方案可用时，也可以解决顶级问题。

归纳算法不是从顶层问题开始的。它立即解决了一个“简单”的问题，并首先解决了这个问题。然后该解决方案用于解决下一个问题......等等。

确实，解决子问题的顺序对于两种方法可能是相同的。但是这个顺序并不是将算法定义为自上而下或自下而上的原因。关键是：这是算法首先解决的问题；不是它首先解决的问题。

堆结构

在谈到堆结构时，术语自底向上和自顶向下也以不同的方式使用。然后它们引用首先构建的堆部分。这可能会令人困惑......

尽管有一种（效率较低的）堆构造算法通过使用普通的 heap_insert 算法向堆中添加一个元素来反复增加堆的大小，但这并不是真正的自顶向下算法：

A.buildMaxHeap():
   for i = 0 to n-1:
       A.heapInsert(a[i], i) # second argument is actual size of the heap before insertion

这确实从上到下构建堆，但实际上它从解决最简单的问题开始：创建一个具有一个值的堆。一旦有了它，它就解决了下一个最简单的问题，......等等。这实际上是自下而上算法的一个特征。

推荐阅读