文档章节

【数据结构】回顾优先队列(堆)

NoMasp
 NoMasp
发布于 2015/09/08 21:50
字数 1076
阅读 7
收藏 0

1.优先队列有两项基本操作:插入(insert)和删除最小项(deleteMin),后者的工作是找出、返回和删除优先队列中最小的元素。而insert操作则等价于enqueue(入队),deleteMin则等价于dequeue(出队)。补充:C++提供2个版本的deleteMin,一个删除最小项,另一个在删除最小项的同时在通过引用传递的对象中存储所删除的值。

这里写图片描述

2.优先队列的类接口

template <typename Comparable>
class BinaryHeap
{
public:
    explicit BinaryHeap(int capacity=100);
    explicit BinaryHeap(const vector<Comparable> & items);

    bool isEmpty() const;
    const Comparable & findMin() const;

    void insert(const Comparable & x);
    void deleleMin();
    void deleteMin(Comparable & minItem);
    void makeEmpty();

private:
    int currentSize;
    vector<Comparable> array;
    void buildHeap();
    void percolateDown(int hole);
};

3.插入到一个二叉堆

void insert(const Comparable & x)
{
    if(currentSize==array.size()-1)
        array.resize(array.size()*2);

    int hole=++currentSize;
    for(;hole>1&&x<array[hole/2];hole/=2)
        array[hole] =array[hole/2];
    array[hole]=x;
}

4.在二叉堆中执行deleteMin

void deleteMin()
{
    if(isEmpty())
        throw UnderflowException();

    array[1]=array[currentSize--];
    percolateDown(1);
}

void deleteMin(Comparable & minItem)
{
    if(isEmpty())
        throw UnderflowException();

    minItem=array[1];
    arrary[1]=array[currentSize--];
    percolateDown(1);
}

void percolateDown(int hole)
{
    int child;
    Comparable tmp=array[hole];

    for(;hole*2<=currentSize;hole=child)
    {
        child=hole*2;
        if(child!=currentSize&&array[child+1]<array[child])
            child++;
        if(array[child]<tmp)
            array[hole]=array[child];
        else 
            break;
    }
    array[hole]=tmp;
}

5.左式堆(leftist heap)像二叉堆那样既有结构性质,又有堆序性质。左序堆也是二叉树,它和二叉树的唯一区别是:左式堆不是理想平衡的(perfectly balanced),而且事实上是趋于非常不平衡的。左式堆的性质:对于堆中的每一个结点X,左儿子的零路径至少于右儿子的零路径长一样大。由于左式堆是趋向于加深左路径,因此右路径应该很短,沿左式堆右侧的右路径确实是该堆中最短的路径。否则就会存在一条路径通过某个结点X并取得左儿子,此时X就破坏了左式堆的性质。

6.对左式堆的基本操作是合并(插入只是合并的特殊情形)。左式堆类型声明:

template <typename Comparable>
class LeftistHeap { public: LeftistHeap(); LeftistHeap(const LeftistHeap & rhs); ~LeftistHeap(); bool isEmpty() const; const Comparable & findMin() const; void insert(const Comparable & x); void deleteMin(); void deleteMin(Comparable & minItem); void makeEmpty(); void merge(LeftistHeap & rhs); const LeftistHeap & operator=(const LeftistHeap & rhs); private: struct LeftistNode { Comparable element; LeftistNode *left; LeftistNode *right; int npl; LeftistNode(const Comparable & theElement, LeftistNode * lt=NULL, LeftistNode * rt=NULL,int np=0) :element(theElement),left(lt),right(rt),npl(np){} }; LeftistNode *root; LeftistNode *merge (LeftistNode *h1,LeftistNode *h2); LeftistNode *merge1(LeftistNode *h1,LeftistNode *h2); void swapChildren(LeftistNode *t); void reclainMemory(LeftistNode *t); LeftistNode *clone(LeftistNode *t) const; };

7.合并左式堆的驱动程序和实际程序

void merge(LeftistHeap & rhs)
{
    if(this==&rhs)
        return;

    root=merge(root,rhs.root);
    rhs.root=NULL;
}

LeftistNode * merge(LeftistNode *h1,LeftistNode *h2)
{
    if(h1==NULL)
        return h2;
    if(h2==NULL)
        return h1;
    if(h1->element<h2->element)
        return merge1(h1,h2);
    else 
        return merge1(h2,h1);
}

LeftistNode *merge1(LeftistNode *h1,LeftistNode *h2)
{
    if(h1->left==NULL)
        h1->left=h2;
    else
    {
        h1->right=merge(h1->right,h2);
        if(h1->left->npl<h1->right-np1)
            swapChildren(h1);
        h1->npl=h1->right->npl+1;
    }
    return h1;
}

8.左式堆的insert程序和deleteMin程序

void insert(const Comparable & x) { root=merge(new LeftistNode(x).root);
}

void deleteMin()
{
    if(isEmpty())
        throw UnderflowException();

    LeftistNode *oldRoot=root;
    root=merge(root->left,root->right);
    delete oldRoot;
}

void delteMin(Comparable & minItem)
{
    minItem=findMin();
    deleteMin();
}

9.二项队列不是一棵堆序的树,而是堆序的集合,称为森林(forest)。

这里写图片描述

这里写图片描述

10.二项队列类构架及结点定义:


template <typename Comparable>
class BinomialQueue
{
public:
    BinomialQueue();
    BinomialQueue(const Comparable & item);
    BinomialQueue(const BinomialQueue & rhs);
    ~BinomialQueue();

    bool isEmpty() const;
    const Comparable &  findMin() const;

    void insert(const Comparable & x);
    void deleteMin();
    void deleteMin(Comparable & minItem);

    void makeEmpty();
    void merge(BinomialQueue & rhs);

    const BinomialQueue & operator = (const BinomialQueue & rhs);

private:
    struct BinomialNode
    {
        Comparable element;
        BinomialNode *leftChild;
        BinomialNode *nextSibling;

        BinomialNode(const Comparable & theElement,
                     BinomialNode *lt,BinomialNode *rt)
            :element(theElement).leftchild(lt).nextSiblig(rt){}
    };

    enum {DEFAULT_TREES=1};

    int currentSize;
    vector<BinomialNode*> theTrees;

    int findMinIndex() const;
    int capacity() const;
    BinomialNode * combineTrees(BinomialNode *t1,BinomialNode *t2);
    void makeEmpty(BinomialNode * & t);
    BinomialNode * clone(BinomialNode * t) const;
};

11.在STL中,二叉堆是通过称为priority_queue的类模板实现的,该类模板可以在标准头文件queue中找到。STL 实现了一个最大堆而不是最小堆,因此所访问的项就是最大的项而不是最小的项。其键成员函数如下:

void push(const Object & x);
const Object & top() const;
void pop();
bool empty();
void clear();



感谢您的访问,希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/45619917

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
二叉堆与优先队列

一、优先队列 1.简单介绍 优先队列是一种抽象的数据结构,它与我们生活中的许多场景息息相关。比如我们的电脑或者手机,很多时候我们后台会运行多个程序,当程序过多导致内存急剧减少时,如果...

丶legend
2017/10/13
0
0
算法——优先队列

许多应用程序都需要处理有序的元素,但不一定要求他们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键...

嘿胖丁
2018/03/05
5
0
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
2018/07/12
0
0
JDK源码阅读(一)、PriorityQueue

写在前面,最近准备春招找实习,还有项目要做,一直没更新博客。不过通过这次找实习总结出来一个结论,基础很重要。 唉,这次找实习就当试试水了,总结一下经验,打好基础。秋招再战~ JDK源码...

zq17865815296
2018/03/26
0
0
【堆内存】动态图+代码五分钟轻松理解学会

前言背景 堆(heap)又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。 因为队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。 而堆虽然在堆底插入元...

懿宁19931210
01/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

idea下springboot 项目在static目录下添加文件不生效

idea下springboot 项目在static目录下添加文件不生效 问题描述 是这样子的,我的项目目录结构如下: 我在static目录下,创建了index.html和aaaa.jpg这两个文件。然后,启动服务访问 http://l...

wotrd
昨天
5
0
k8s1.14 一、环境

1. 4台虚拟机 (CentOS Linux release 7.2.1511 (Core) ) 192.168.130.211 master 192.168.130.212 node1 192.168.130.213 node2 192.168.130.214 node3 2. 设置服务器hostname 2.1 设置本机......

ThomasCheng
昨天
3
0
盖茨:如果我现在开创一家公司 将会专注于AI

新浪科技讯,北京时间 6 月 26 日凌晨消息,微软联合创始人比尔·盖茨(Bill Gates)在周一接受采访时表示,如果他今天从哈佛大学辍学并开创一家新公司,那么这家公司将会专注于人工智能(A...

linuxCool
昨天
1
0
聊聊feign的Retryer

序 本文主要研究一下feign的Retryer Retryer feign-core-10.2.3-sources.jar!/feign/Retryer.java public interface Retryer extends Cloneable { /** * if retry is permitted, retur......

go4it
昨天
10
0
HyperLogLog简介

  (1)HyperLogLog简介      在Redis 在 2.8.9 版本才添加了 HyperLogLog,HyperLogLog算法是用于基数统计的算法,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个...

SEOwhywhy
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部