9.1 最小-最大堆

  • 「双端优先队列 double-ended priority queue」 是一种支持如下操作的数据结构:

    1. 插入一个具有任意关键字值的元素。
    2. 删除关键字值最大的元素。
    3. 删除关键字值最小的元素。
  • 采用 「最小-最大堆 min-max heap」 可以同时支持上述全部操作。最大堆无法删除最小的元素,最小堆无法删除最大的元素。 「最小-最大堆」是一个满足如下条件的完全二叉树:该二叉树不为空,其上的每个元素都有一个称为关键字的域。针对该关键字域,二叉树的各层教体委最小层和最大层,且根结点位于最小层。设 xx 是最小-最大堆中的任意一个结点,如果 xx 位于最小层,那么 xx 就是以 xx 为根结点的二叉树中关键字值最小的结点,称该结点为最小结点。类似地,如果 xx 位于最大层,那么 xx 就是以 xx 为根结点的二叉树中关键字值最大的结点,称该结点为最大结点。

9-1

最小-最大堆

  • 『插入元素』 假设要在上图中插入关键字值为 5 的元素。与其他堆一样,最小-最大堆上的插入算法沿着新插入的结点 jj 到根结点的路径比较关键字值。比较新结点 jj 的关键字值 5 与其父结点关键字值 10,可以看到,由于关键字值为 10 的结点位于最小层,且 5 < 10,所以 5 一定小于从结点 jj 到根结点路径上的所有最大结点的关键字,因此,只需检查从 jj 到根的路径上的最小结点的关键字值。首先,将关键字值为 10 的元素移到结点 jj。然后,把关键字值为 7 的元素移到 10 原来的位置;最后,将关键字值为 5 的新元素插入到根结点。插入过程如下图。

9-2

9-3

函数 min_max_insert 实现了最小-最大堆的插入过程,其中用到了三个函数:verify_max, verify_min, level。函数 level 确定一个结点是位于最小层还是最大层;如果位于最小层,则返回 false,而位于最大层,则返回 true。函数 verify_max 从一个最大结点开始,沿着从 ii 到根的路径,依次检查最大结点,查找插入元素 item 的正确结点。函数 verify_minverify_max 类似,只是 verify_min 是查找最小结点。函数 min_max_insert 的时间复杂度为 O(logn)O(\log n)

void min_max_insert(element heap[], int *n, element item)
{
    int parent;
    (*n) ++;
    if (*n == MAX_SIZE) {
        fprintf(stderr, "The heap is full\n");
        exit(1);
    }
    parent = (*n) / 2;
    if (!parent)
        heap[1] = item;
    else switch (level(parent)) {
        case false: // min level
            if (item.key < heap[parent].key) {
                heap[*n] = heap[parent];
                verify_min(heap, parent, item);
            }
            else
                verify_max(heap, *n, item);
            break;
        case true: // max level
            if (item.key > heap[parent].key) {
                heap[*n] = heap[parent];
                verify_max(heap, parent, item);
            }
            else
                verify_min(heap, *n, item);
    }
}

void verify_max(element heap[], int i, element item)
{
    int grandparent = i/4;
    while (grandparent)
        if (item.key > heap[grandparent].key) {
            heap[i] = heap[grandparent];
            i = grandparent;
            grandparent /= 4;
        }
        else
            break;
    heap[i] = item;
}

bool level(element item)
{
    return !((log(item.key) / log(2)) % 2);
}
  • 『删除最小元素』 整个堆中最小的结点就在根结点中,所以先删除根结点。再将下标最大的结点 item 删除(相当于第一张图中关键字值为 12 的结点),并将这个结点 item 重新插入到这个根结点为空的堆中,将这个插入过程分为以下集中情况:

    1. 根结点没有儿子结点。此时,可以将 item 直接插入根结点中。
    2. 根结点至少有一个儿子结点。此时,最小-最大堆中关键字值最小的结点一定出现在根结点的儿子结点或后代结点中。为了确定其中的具有最小关键字值的结点,设具有最小关键字值结点的下标为 kk,则需要考虑下列几种情况:
      1. item.key <= heap[k].key。此时,由于 heap 中没有关键字值比 item.key 更小的结点,所以,item 直接插入到根结点。
      2. item.key > heap[k].keykk 是根结点的儿子结点。此时,由于 kk 是最大结点,所以其后代结点中不可能有关键字值大于 heap[k].key 的结点。从而也就没有关键字值大于 item.key 的结点。所以可以把元素 heap[k] 移到根结点,并将 item 插入 kk 结点。
      3. item.key > heap[k].keykk 是根结点的后代结点。此时,也可以先把元素 heap[k] 移到根结点,并将 item 插入结点 kk。然后考察结点 kk 的父结点 parent:如果 item.key > heap[parent].key,则将 heap[parent] 与元素 item 互换,这样就保证了最大结点 parent 的关键字值在以 parent 为根的子堆中是最大的。此时,问题转化为将 item 插入到以 kk 为根的子堆中,而且这个子堆的根结点 h[k] 已腾空。这与初始时将 item 插入到根结点为空的最小-最大堆完全一样,因此可以重复上述处理过程。

    函数 delete_min 实现了删除最小元素,它调用了函数 min_child_grandchild(i),用以确定 i 结点的所有儿子和后代结点中关键字值最小的结点。如果 i 的儿子结点和后代结点的最小结点相等,则返回儿子结点的地址。程序段中并没有实现函数 min_child_grandchild。函数 delete_min 的时间复杂度是 O(logn)O(\log n)

element delete_min(element heap[], int *n)
{
    int i, last, k, parent;
    element temp, x;

    if (!(*n)) {
        fprintf(stderr, "The heap is empty\n");
        heap[0].key = INT_MAX;
        return heap[0];
    }
    heap[0] = heap[1];
    x = heap[(*n)--];
    for (i = 1, last = (*n) / 2; i <= last;) {
        k = min_child_grandchild(i, *n);
        if (x.key <= heap[k].key) break;
        heap[i] = heap[k];
        if (k <= 2*i+1) {
            i = k;
            break;
        }
        parent = k/2;
        if (x.key > heap[parent].key)
            SWAP(heap[parent], x, temp);
        i = k;
    }
    heap[i] = x;
    return heap[0];
}

results matching ""

    No results matching ""