您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

左倾堆 leftist heap

左倾堆(左偏树)和是堆的一种;和普通的二叉堆不同,它是一种可合并堆。可合并堆相比于普通的二叉堆在对两个堆进行合并的操作上具有很大的优势:对于基本的二叉堆合并,时间复杂度为O(n), 而对于可合并堆,其时间复杂度为O(log2n).

 

#include<iostream>
using namespace std;
 
struct TreeNode{
    int key;//key为键值,这里是按照key最小值优先
    int npl;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int k){
        key = k;
        npl = 0;
        left = right = NULL;
    }
};
void Swap(TreeNode* node1, TreeNode* node2){
    TreeNode* tmp = node1;
    node1 = node2;
    node2 = tmp;
}
 
//左倾堆的合并操作
TreeNode* Merge(TreeNode* heap1, TreeNode* heap2){
    //如果其中一个为空堆,则直接返回另外一个
    if (!heap1)
        return heap2;
    if (!heap2)
        return heap1;
    //选择“较小堆”,将其根节点作为新堆的根节点
    if (heap1->key > heap2->key){
        Swap(heap1, heap2);
    }
    //将较小堆的右子堆和较大堆进行合并,并置为较小堆的右子堆
    heap1->right = Merge(heap1->right, heap2);
    if (heap1->left == NULL || (heap1->left && heap1->right && heap1->left->npl < heap1->right->npl)){ //如果堆的根节点的左子结点的npl小于右子节点的npl,则交换左右子节点
        Swap(heap1->left, heap1->right);
    }
 
    if (heap1->right == NULL)
        heap1->npl = 1;
    else
        heap1->npl = heap1->right->npl + 1; //新堆的npl设为右子节点的npl +1
    return heap1;
}
 
//将元素k插入堆 heap中,即元素入队。 注意这里使用指针的引用
void Enqueue(TreeNode*& heap, int k){
    if (!heap){
        heap = new TreeNode(k);
        return;
    }
    TreeNode* new_heap = new TreeNode(k);
    heap = Merge(heap, new_heap);
}
 
//元素出队,注意这里使用指针的引用
int Dequeue(TreeNode*& heap){
    int result = heap->key;
    heap = Merge(heap->left, heap->right);
    return result;
}

https://www.cnblogs.com/gtarcoder/p/4725346.html


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进