0

我正在为我的期末考试而学习，但不确定我6, 7, 57, 54, 96, 3, 9, 4, 2, 8, 32是否正确插入了这些值。我最终得到一棵树，看起来像：

                                     96
                                   /    \
                                  57     9
                                 /  \   / \
                                6   54 3   7
                               / \  / \
                               4 2 8   32

谁能告诉我这是否正确，或者是否没有指出我在哪里搞砸了？谢谢！

4

2 回答 2

2

它是正确的。为什么你认为你还是搞砸了？

于 2013-08-06T22:49:23.370 回答
1

是的，你的解决方案是正确的

只要您在表示二叉堆的列表末尾添加新元素，然后在该元素上应用 heapify。

Heapify 应该将元素与它的父元素进行比较，如果它更大，它应该交换这些元素并继续前进，直到你到达根。

这里有一些阶段：

6       -->              7       -->    57
                        /              /  \
                       6              6    7

这是一个Java示例：

public class BinaryMinHeap {



    public void insert(int value) {
                if (heapSize == data.length)
                      throw new HeapException("Heap's underlying storage is overflow");
                else {
                      heapSize++;
                      data[heapSize - 1] = value;
                      heapify(heapSize - 1);
                }
          }    

          …

    private void heapify(int nodeIndex) {
                int parentIndex, tmp;
                if (nodeIndex != 0) {
                      parentIndex = getParentIndex(nodeIndex);
                      if (data[parentIndex] < data[nodeIndex]) {
                            tmp = data[parentIndex];
                            data[parentIndex] = data[nodeIndex];
                            data[nodeIndex] = tmp;
                            heapify(parentIndex);
                      }
                }
          }
    }

代码来源：这里

于 2013-08-06T22:54:00.590 回答