13.2.堆结构

发表于 更新于 分类于 ， 阅读次数： 本文字数： 539 阅读时长 ≈ 2 分钟

\(13.2\)堆结构

1.堆结构的引入

  由先前的分析，我们得出拥有最佳运行时间的是\(BST\)。然而，对\(BST\)进行修饰后，我们可以得到更好的运行时间。

  我们定义我们的二叉堆遵循以下性质：

  • 最小性：每个节点都小于等于它的儿子节点。
  • 完全性：缺失的元素只能位于堆的底部；堆中元素排列应尽可能左偏。

  如图，绿色的堆是符合条件的，而红色的是不符合条件的。

2.树的表示

  我们可以用如下的方式表示一棵树： * \(Tree1A\)：用指针表示： 

1
2
3
4
5
6
7
public class Tree1A<Key> {
  Key k;
  Tree1A left;
  Tree1A middle;
  Tree1A right;
  ...
}

  • \(Tree1B\)：用父节点元素与数组混合表示： 
    1
    2
    3
    4
    5
    public class Tree1B<Key> {
      Key k;
      Tree1B[] children;
      ...
    }

  • \(Tree1C\)：用父节点元素、指向第一个孩子的元素和\(next\)指针(\(sibling\))表示： 
    1
    2
    3
    4
    5
    6
    public class Tree1C<Key> {
      Key k;
      Tree1C favoredChild;
      Tree1C sibling;
      ...
    }

  这些表示树的方式都直接引用(\(explicit\;reference\))了节点的儿子。下面介绍一些不存储对儿子的引用的表示方式：

  • \(Approach\;2\)
    • 我们可以用类似并查集的表示方式，创建一个\(parents\)数组和一个\(key\)数组： 
      1
      2
      3
      4
      5
      public class Tree2<Key> {
        Key[] keys;
        int[] parents;
        ...
      }

  当我们假定我们的堆是完全的时，我们还可以只用一个一维数组来表示： * \(Approach\;3\) 

1
2
3
4
public class TreeC<Key> {
  Key[] keys;
  ...
}

  这种树的表示方法十分简便，我们在堆的实现中将使用这种方法。

3.swim方法

  在堆的构建中，我们定义如下的swim方法： 

1
2
3
4
5
6
public void swim(int k) {
    if (keys[parent(k)] ≻ keys[k]) {
       swap(k, parent(k));
       swim(parent(k));              
    }
}

  如果对\(Approach\;3\)进行观察的话，可以发现如下规律：

\[ \begin{cases} parent=i\\ leftchild=2i+1\\ rightchild=2i+2 \end{cases} \]

  如果我们让数组的\(0\)位置为空(不放置元素)，则可以得到更简洁的规律：

\[ \begin{cases} parent=i\\ leftchild=2i\\ rightchild=2i+1 \end{cases} \]

  这样，我们就可以将数组中的元素与树上的元素一一对应了。