1

抱歉，如果标题中的术语已关闭。我试图通过更频繁地使用它们来更好地理解这些术语。

无论如何，我目前正在一个数据结构类的实验室（使用 C++）中工作，我必须构建一个三元堆并将其与已经提供给我们的二元堆进行比较。由于我有一些额外的时间，我想解决我的代码中的一些细节，以便它尽可能高效地运行。

我最担心的是我正在使用的 if-else 语句的数量。实际上，我必须花十分钟在纸上组织它们的布局，以免我感到困惑。（我不是在抱怨，我只是不知道这是否是解决问题的最佳方法。）

template<class T>
void TernaryHeap<T>::trickleDown(int i) {
do {
    int j = -1;

    int r = right(i);
    if (r < n && compare(a[r], a[i]) < 0) {

        int l = left(i);
        if (compare(a[l], a[r]) < 0) {
            j = l;
        } else {
            j = r;
        }

        int m = mid(i);
        if (compare(a[m], a[r]) < 0) {
            j = m;
        } else { 
            j = r; 
        } 

    } else {

        int l = left(i);
        if (l < n && compare(a[l], a[i]) < 0) {

            int m = mid(i);
            if (compare(a[m], a[l]) < 0) {
                j = m;
            } else {
                j = l;
            }
        }
    }
    if (j >= 0) a.swap(i, j);
    i = j;
} while (i >= 0);
}
4

1 回答 1

0

您将如何找到 2 元素数组中的最小元素？你可能会发现一个if-else就足够了。

现在为一个 3 元素数组做同样的事情。您只是添加更多条件吗？还是您只是编写一个通用算法来处理任何大小的数组？

您的“筛选”算法分两步完成：找到最小的元素，然后将其与当前元素交换。您通过简单地添加更多测试将二进制堆概括为三元堆，而您可能应该采用更通用的解决方案。如果你去一个四元堆怎么办？您会添加更多if-else测试吗？

于 2013-10-15T04:54:26.513 回答