5.6 堆

  • 「最大树 max tree」 是指在树中,(如果)一个结点有儿子结点,其关键字值都不小于其儿子结点的关键字值。
  • 「最大堆 max heap」 是一棵完全二叉树,也是一棵最大树。
  • 「最小树 min tree」 是指在树中,(如果)一个结点有儿子结点,其关键字值都不大于其儿子结点的关键字值。
  • 「最小堆 min heap」 是一棵完全二叉树,也是一棵最小树。

5-19

最大堆的例子

5-20

最小堆的例子

使用数组来表示堆时,一般不使用数组的第 0 个位置,即上图最大堆的第一个例子中,heap[1] 表示根结点 14,heap[2] 表示结点 12。

  • 「ADT 最大堆」 MaxHeap 是把 n>0n > 0 个元素组织起完全二叉树,使每个结点关键字值至少不少于其儿子结点的关键字值。
class MaxHeap
{
    MaxHeap Create(uint max_size) {
        // 创建一个空堆,能够保存 max_size 个元素
    }
    bool HeapFull(MaxHeap heap, uint n) {
        if (n == max_size) return true;
        else return false;
    }
    MaxHeap Insert(MaxHeap heap, Element item, uint n) {
        if (!HeapFull(heap, n)) 将 item 插入 heap,返回结果堆
        else return 错误
    }
    bool HeapEmpty(MaxHeap heap, uint n) {
        if (n > 0) return true;
        else return false;
    }
    Element Delete(MaxHeap heap, uint n) {
        if (!HeapEmpty(heap, n)) return 堆中最大元素的例子,并将其从堆中删除
        else return 错误
    }
}
  • 「优先级队列 priority queue」 与「队列」不同的是,「优先级队列」只对最高(或最低)优先级的元素进行删除。但是在任何时候,都可以把任意优先级的元素插入到优先级队列。
  • 『优先级队列的存储表示』 如下表,如果使用无序数组,把新的元素插入到数组的尾端,因此插入操作时间复杂度为 Θ(1)\Theta(1),删除操作必须先找到最大关键值的元素,查找时间是 Θ(n)\Theta(n),而移动数组的时间是 O(n)O(n)。如果使用有序数组,可以在 Θ(1)\Theta(1) 时间内删除元素,但是,插入元素需要移动部分或全部元素,时间是 O(n)O(n)。若都改为单向链表,节省的只有移动元素的时间。但是如果把优先级队列存储表示为堆,那么无论是插入还是删除操作都能在 O(log2n)O(\log_2n) 内完成。
存储表示 插入操作 删除操作
无序数组 Θ(1)\Theta(1) Θ(n)\Theta(n)
无序单向链表 Θ(1)\Theta(1) Θ(n)\Theta(n)
有序数组 O(n)O(n) Θ(1)\Theta(1)
有序单向链表 O(n)O(n) Θ(1)\Theta(1)
最大堆 O(log2n)O(\log_2n) O(log2n)O(\log_2n)
  • 『最大堆的插入操作』 如下图说明了最大堆的插入操作,新的结点的插入位置需要满足堆的定义:新插入一个结点首先符合完全二叉树的定义插入到最深的位置作为其初始位置,然后不断与其父结点比较,若大于其父结点,则交换,直到符合堆的定义。

5-21

最大堆的插入操作

函数 insert_max_heap 首先检测堆是否满,如果不满,则设 i 等于新堆的大小 n+1。现在,必须确定 item 在堆中的正确位置。while 循环从最大堆的新叶子结点开始,沿着到根结点的路径,直到根结点,或者位置 i,使其父结点 i/2 的值不小于要插入的值。由于堆是一棵完全二叉树,具有 nn 个元素,其高度为 log2(n+1)\lceil \log_2(n+1) \rceil。这就意味着 while 循环要重复 O(log2n)O(\log_2n) 次。因此,插入函数的时间复杂度为 O(log2n)O(\log_2n)

#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS - 1)
#define HEAP_EMPTY(n) (!n)
typedef struct {
    int key;
    // 结点的其他域
} element;
element heap(MAX_ELEMENTS);
int n = 0;

void insert_max_heap(element item, int *n)
{
    int i;
    if (HEAP_FULL(*n)) {
        fprintf(stderr, "The heap is full. \n");
        exit(1);
    }
    i = ++(*n);
    // 与其父结点比较(heap[i/2] 为其父结点)
    while ((i != 1) && (item.key > heap[i/2].key)) {
        heap[i] = heap[i/2];
        i /= 2;
    }
    heap[i] = item;
}
  • 『最大堆的删除操作』 如下图说明了最大堆的删除操作,删除时,总是从堆的根结点删除元素。为了满足完全二叉树的定义,需要用数组存储的尾结点补位被删除的根结点,然后再以同样的与父结点比较的方式重新排列以符合最大堆的定义。 函数 delete_max_heap 通过下移堆中的元素来实现删除操作,比较并交换父结点与儿子结点,直到堆被重新建立起来。由于包含 nn 个元素的堆的高度为 log2(n+1)\lceil \log_2(n+1) \rceil,因此,函数 delete_max_heap 中的 while 循环重复 O(log2n)O(\log_2n) 次。因此,删除操作时间复杂度为 O(log2n)O(\log_2n)

5-22

最大堆的删除操作

element delete_max_heap(int *n)
{
    int parent, child;
    element item, temp;
    if (HEAP_EMPTY(*n)) {
        fprintf(stderr, "The heap is empty\n");
        exit(1);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n) {
        if ((child < *n) && (heap[child].key < heap[child+1].key))
            child++;
        if (temp.key >= heap[child].key) break;
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return temp;
}

results matching ""

    No results matching ""