c++ - 在三元堆中实现滴流操作的最有效方法

Question

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

无论如何，我目前正在数据结构类(使用 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);
}

Answer 1

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

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

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