斜堆

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_36670529/article/details/102455406

斜堆的介绍

斜堆(Skew heap)也叫自适应堆(self-adjusting heap),它是左倾堆的一个变种。和左倾堆一样,它通常也用于实现优先队列。它的合并操作的时间复杂度也是O(log n)。

相比于左倾堆,斜堆的节点没有"零距离"这个属性。除此之外,它们斜堆的合并操作也不同。斜堆的合并操作算法如下: (01) 如果一个空斜堆与一个非空斜堆合并,返回非空斜堆。 (02) 如果两个斜堆都非空,那么比较两个根节点,取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。 (03) 合并后,交换新堆根节点的左孩子和右孩子。 第(03)步是斜堆和左倾堆的合并操作差别的关键所在,如果是左倾堆,则合并后要比较左右孩子的零距离大小,若右孩子的零距离 > 左孩子的零距离,则交换左右孩子;最后,在设置根的零距离。

很多都是和左倾堆很相似的!

#include<stdio.h>
#include<stdlib.h>
typedef int Type;
     
typedef struct _SkewNode{
Type   key;                // 关键字(键值)
struct _SkewNode *left;    // 左孩子
struct _SkewNode *right;   // 右孩子
}SkewNode, *SkewHeap;
     
     
/*
* 合并"斜堆x"和"斜堆y"
*
* 返回值:
*     合并得到的树的根节点
*/
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y)
{
if(x == NULL)
return y;
if(y == NULL)
return x;
     
// 合并x和y时,将x作为合并后的树的根;
// 这里的操作是保证: x的key < y的key
if(x->key > y->key)
swap_skewheap_node(x, y);
     
// 将x的右孩子和y合并,
// 合并后直接交换x的左右孩子,而不需要像左倾堆一样考虑它们的npl。
SkewNode *tmp = merge_skewheap(x->right, y);
x->right = x->left;
x->left  = tmp;
     
return x;
}
     
/*
* 合并"斜堆x"和"斜堆y"
*
* 返回值:
*     合并得到的树的根节点
*/
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y)
{
if(x == NULL)
return y;
if(y == NULL)
return x;
     
// 合并x和y时,将x作为合并后的树的根;
// 这里的操作是保证: x的key < y的key
if(x->key > y->key)
swap_skewheap_node(x, y);
     
// 将x的右孩子和y合并,
// 合并后直接交换x的左右孩子,而不需要像左倾堆一样考虑它们的npl。
SkewNode *tmp = merge_skewheap(x->right, y);
x->right = x->left;
x->left  = tmp;
     
return x;
}
     
    /*
     * 取出根节点
     *
     * 返回值:
     *     取出根节点后的新树的根节点
     */
    SkewNode* delete_skewheap(SkewHeap heap)
    {
        SkewNode *l = heap->left;
        SkewNode *r = heap->right;
     
        // 删除根节点
        free(heap);
     
        return merge_skewheap(l, r); // 返回左右子树合并后的新树
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 红黑树

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    于小勇
  • tf.train

    1、tf.train.queue_runner.add_queue_runner函数

    于小勇
  • tensorflow的图像预处理函数

    对图像进行预处理,可以尽量避免模型受到。大部分图像识别问题中,通过图像预处理过程可以提高模型的准确率。

    于小勇
  • CountDownLatch源码分析

    CountDownLatch源码分析之前,首先看一看CountDownLatch的用法,我们通过一段代码来说明CountDownLatch的基本用法,代码如下。

    大猫的Java笔记
  • 老树新花-Java异步服务开发

    摘要 饿了么资深Java工程师朱杰从同步异步概念介绍、使用Java来开发异步化服务、回调监听模式所遇到的问题和解决这三方面来我们全面解读Java异步服务开发。 ...

    IT大咖说
  • Java 异步编程导论

    异步编程是可以让程序并行运行的一种手段,其可以让程序中的一个工作单元与主应用程序线程分开独立运行,并且等工作单元运行结束后通知主应用程序线程它的运行结果或者失败...

    加多
  • Java 异步编程导论

    异步编程是可以让程序并行运行的一种手段,其可以让程序中的一个工作单元与主应用程序线程分开独立运行,并且等工作单元运行结束后通知主应用程序线程它的运行结果或者失败...

    纯洁的微笑
  • DKhadoop添加删除节点的易用性探讨

    Hadoop作为搭建大数据处理平台的重要“基石”,关于它的分析和讲解的文章已经有很多了。Hadoop本身是一分布式的系统,因此在安装的时候,需要多每一个节点进行...

    IT小白龙
  • 【CVM】Linux 主网卡配置双IP

    GATEWAY 写法为内网IP最后一位改为 1,即内网IP 172.17.0.11,GATEWAY 即为 172.17.0.1

    Hanzo
  • 游戏数据埋点二三事

    ? 导语:本文宽泛的梳理了游戏产品数据相关的数据埋点内容,包含游戏数据埋点的一些原则和技巧。主要面向刚刚接触游戏数据业务的新人,希望这篇文章能有所帮助。 数据...

    腾讯技术工程官方号

扫码关注云+社区

领取腾讯云代金券