纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。

在之前的文章中,我们基于完全二叉树(complete binary tree)实现了堆,这样的堆叫做二叉堆(binary heap)。binary heap有一个基本要求: 每个节点的优先级大于两个子节点的优先级。在这一要求下,堆的根节点始终是堆的元素中优先级最高的元素。此外,我们实现了delete_min()操作,从堆中取出元素;insert()操作,向堆中插入元素。

现在,我们考虑下面的问题: 如何合并(merge)两个堆呢? 一个方案是从第一个堆中不断取出一个元素,并插入到第二个堆中。这样,我们需要量级为n的操作。我们下面要实现更有效率的合并。

左倾堆 (Leftist Heap)

左倾堆基于二叉树(binary tree)。左倾堆的节点满足堆的基本要求,即(要求1)每个节点的优先级大于子节点的优先级。与二叉堆不同,左倾堆并不是完全二叉树。二叉堆是非常平衡的树结构,它的每一层都被填满(除了最下面一层)。左倾堆则是维持一种不平衡的结构: 它的左子树节点往往比右子树有更多的节点。

不平衡

左倾堆的每个节点有一个附加信息,即null path length (npl)。npl是从一个节点到一个最近的不满节点的路径长度(不满节点:两个子节点至少有一个为NULL)。一个叶节点的npl为0,一个NULL节点的npl为-1。

各个节点的npl (这里显示的不是元素值)

根据npl的定义,我们有推论1: 一个节点的npl等于子节点npl中最小值加1: npl(node) = min(npl(lchild), npl(rchild)) + 1

有了npl的概念,我们可以完整的定义左倾堆。左倾堆是一个符合下面要求的二叉树:

  • 要求1: 每个节点的优先级大于子节点的优先级。
  • 要求2: 对于任意节点的左右两个子节点,右子节点的npl不大于左子节点的npl。

左倾堆的性质

从上面的要求1和2可以知道,左倾堆的任意子树也是一个左倾堆。

由于左倾堆的特征,左倾堆的右侧路径(right path)较短。右侧路径是指我们从根节点开始,不断前往右子节点所构成的路径。对于一个左倾堆来说,右侧路径上节点数不大于任意其他路径上的节点数,否则,将违反左倾堆的要求2。

我们还可以证明推论2,如果一个左倾堆的右侧路径上有r个节点,那么该左倾堆将至少有2r-1个节点。我们采用归纳法证明:

  • r = 1, 右侧路径上有一个节点,所以至少有21-1个节点
  • 假设任意r, 左倾堆至少有2r-1节点。那么对于一个右侧路径节点数为r+1的左倾堆来说,根节点的右子树的右侧路径有r个节点。根节点的左子树的右侧路径至少有r个节点。根据假设,该左倾堆将包括: 
    • 右子树:至少有2r-1个节点
    • 左子树: 至少有2r-1个节点
    • 1个根节点
  • 因此,对于r+1,整个左倾堆至少有2r+1-1个节点。证明完成

换句话说,一个n节点的的左倾堆,它的右侧路径最多有log(n+1)个节点。如果对右侧路径进行操作,其复杂度将是log(n)量级。

我们将沿着右侧路径进行左倾堆的合并操作。合并采用递归。合并如下:

  1. (base case) 如果一个空左倾堆与一个非空左倾堆合并,返回非空左倾堆
  2. 如果两个左倾堆都非空,那么比较两个根节点。取较小的根节点为新的根节点(满足要求1),合并较小根节点堆的右子堆与较大根节点堆。
  3. 如果右子堆npl > 左子堆npl,互换右子堆与左子堆。
  4. 更新根节点的npl = 右子堆npl + 1

上面的合并算法调用了合并操作自身,所以是递归。由于我们沿着右侧路径递归,所以复杂度是log(n)量级。

左倾堆的实现

上面可以看到,左倾堆可以相对高效的实现合并(merge)操作。

其他的堆操作,比如insert, delete_min都可以在merge基础上实现:

  • 插入(insert): 将一个单节点左倾堆(新增节点)与一个已有左倾堆合并。
  • 删除(delete_min): 删除根节点,将剩余的左右子堆合并。
/* By Vamei */

/* 
 * leftist heap
 * bassed on binary tree 
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

struct node {
    ElementTP element;
    int npl;
    position lchild;
    position rchild;
};

typedef struct node *LHEAP;

LHEAP insert(ElementTP, LHEAP);
ElementTP find_min(LHEAP);
LHEAP delete_min(LHEAP);
LHEAP merge(LHEAP, LHEAP);
static LHEAP merge1(LHEAP, LHEAP);
static LHEAP swap_children(LHEAP);

int main(void)
{
    LHEAP h1=NULL;
    LHEAP h2=NULL;
    h1 = insert(7, h1);
    h1 = insert(3, h1);
    h1 = insert(5, h1);

    h2 = insert(2, h2);
    h2 = insert(4, h2);
    h2 = insert(8, h2);

    h1 = merge(h1, h2);
    printf("minimum: %d\n", find_min(h1));
    return 0;
}

/*
 * insert:
 * merge a single-node leftist heap with a leftist heap
 * */
LHEAP insert(ElementTP value, LHEAP h)
{
    LHEAP single;
    single = (position) malloc(sizeof(struct node));

    // initialze
    single->element  = value;
    single->lchild   = NULL;
    single->rchild   = NULL;

    return  merge(single, h);
}

/*
 * find_min:
 * return root value in the tree
 * */
ElementTP find_min(LHEAP h)
{
    if(h != NULL) return h->element;
    else exit(1);
}

/*
 * delete_min:
 * remove root, then merge two subheaps
 * */
LHEAP delete_min(LHEAP h)
{
    LHEAP l,r;
    l = h->lchild;
    r = h->rchild;
    free(h);
    return merge(l, r);
}

/*
 * merge two leftist heaps
 * */
LHEAP merge(LHEAP h1, LHEAP h2) 
{

    // if one heap is null, return the other
    if(h1 == NULL) return h2;
    if(h2 == NULL) return h1;

    // if both are not null
    if (h1->element < h2->element) { 
        return merge1(h1, h2);
    }
    else {
        return merge1(h2, h1);
    }
}

// h1->element < h2->element
static LHEAP merge1(LHEAP h1, LHEAP h2)
{
    if (h1->lchild == NULL) { 
        /* h1 is a single node, npl is 0 */
        h1->lchild = h2; 
    /* rchild is NULL, npl of h1 is still 0 */
    }
    else {
        // left is not NULL
    // merge h2 to right
    // swap if necessary
        h1->rchild = merge(h1->rchild, h2);
    if(h1->lchild->npl < h1->rchild->npl) {
        swap_children(h1);
    }
        h1->npl = h1->rchild->npl + 1; // update npl
    }
    return h1;
}

// swap: keep leftist property
static LHEAP swap_children(LHEAP h) 
{
    LHEAP tmp;
    tmp       = h->lchild;
    h->lchild = h->rchild;
    h->rchild = tmp;
}

总结

左倾堆利用不平衡的节点分布,让右侧路径保持比较短的状态,从而提高合并的效率。

在合并过程,通过左右互换,来恢复左倾堆的性质。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

SimpleDateFormat 如何安全的使用?

看到这条我立马就想起了我实习的时候有个项目里面就犯了这个错误,记得当时是这样写的:

11110
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

1.6K100
来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

12220
来自专栏大闲人柴毛毛

剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

38250
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

9840
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

21160
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

22090
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

24150
来自专栏一个会写诗的程序员的博客

List.remove 报错 UnsupportedOperationException

Java中List.remove(removeRange,clear类似) 报出 UnsupportedOperationException 的错误。原来该Li...

9520
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

217100

扫码关注云+社区

领取腾讯云代金券