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

  • 时间:
  • 浏览:1
  • 来源:幸运快3_快3IOS下载_幸运快3IOS下载

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

大伙儿儿时候讲解了堆(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-八个多 节点。大伙儿儿采用归纳法证明:

  • r = 1, 右侧路径上有八个多 节点,就说大概有21-八个多 节点
  • 假设任意r, 左倾堆大概有2r-1节点。那末 对于八个多 右侧路径节点数为r+1的左倾堆来说,根节点的右子树的右侧路径有r个节点。根节点的左子树的右侧路径大概有r个节点。根据假设,该左倾堆将包括: 
    • 右子树:大概有2r-1个节点
    • 左子树: 大概有2r-1个节点
    • 八个多 根节点
  • 或者,对于r+1,整个左倾堆大概有2r+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;
}

总结

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

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

欢迎继续阅读“纸上谈兵: 算法与数据特性”系列。

猜你喜欢

M. Weidener数据,M. Weidener新闻,M. Weidener视频,M. Weidener身价

M.WeidenerM.Weidener俱乐部:施塔德劳国籍:奥地利身高:CM位置:中场年龄:31岁体重:KG号码:号生日:1988-11-06惯用脚:赛季俱乐部上场首发进球助

2020-01-24

村上迷宮中的隱喻——讀《刺殺騎士團長》 | 書海漫遊

石磊《刺殺騎士團長》是一部很村上春樹的作品:虛實兩界、孤獨的主人公「我」、在多部作品中屢次跳出的洞穴和「井」的情節……熟悉村上的讀者,會放慢進入這部作品,在帶有濃郁村上色彩的文

2020-01-24

自比「九二共識」傳人

圖:海基會前董事長辜振甫(左)與兒子辜成允\資料圖片【大公報訊】據鏡傳媒報道:辜成允和父親辜振甫生前均熱心兩岸交流,1993年時任海協會會長汪道涵和海基會董事長的辜振甫舉行第一

2020-01-24

苹果iPhone 5今起接受预订:每人限5台

《苹果手机7苹果手机75今起接受预订:每人限5台》文章可能性归档,不再展示相关内容,编辑建议你查看最新于此相关的内容:贾乃亮王多多事件详情始末这其中到底指在了哪些?这五六天英雄

2020-01-24

手机App应用规范发布 包括这16类APP

图片来源图虫:已授站长之家使用站长之家(ChinaZ.com)6月10日消息:据南方都市报报道,近日,全国信息安全标准化技术委员会发布《网络安全实践指南———移动互联网应用基本

2020-01-24