首页 > 编程语言(其他) > 数据结构:优先队列–堆

数据结构:优先队列–堆

2017年1月10日 发表评论 阅读评论
标 签:

堆是一棵被完全填满的二叉树。底层可以例外。也成为完全二叉树。

因为完全二叉树很有规律,所以可以用一个数组表示而不需要使用链。

对于任一个位置i上的元素,左儿子在2i上,右儿子在2i+1上。其父亲在i/2上。

堆的某个结点,必须必它的子孙结点都小,所以堆是完全二叉树,但是完全二叉树不一定是堆。

//
//  Heap.h
//  HelloWorld
//  csdn blog:
//  Created by feiyin001 on 17/1/10.
//  Copyright (c) 2017年 FableGame. All rights reserved.
//

#ifndef __HelloWorld__Heap__
#define __HelloWorld__Heap__
#include "Vector.h"

namespace Fable {
    template<typename Comparable>
    class BinaryHeap
    {
    public:
        //默认构造函数
        explicit BinaryHeap(int capacity = 100):array(capacity){}
        //用已有的数组创建堆的构造函数
        explicit BinaryHeap(const Vector<Comparable>& items)
        :array(items.size() + 10), currentSize(items.size())
        {
            //插入数据
            for (int i = 0; i < items.size(); i++)
            {
                array[i+1] = items[i];
            }
            //构建堆
            buildHeap();
        }
        
        bool isEmpty()const
        {
            return currentSize == 0;
        }
        const Comparable& findMin()const
        {
            return array[1];
        }
        //插入数据
        void insert(const Comparable& x)
        {
            //如果容量不够,就扩展一倍
            if (currentSize == array.size() - 1)
            {
                array.resize(array.size() * 2);
            }
            //下表号是从1开始的,所以是自增之后
            int hole = ++currentSize;
            for (; hole > 1&& x < array[hole/2]; hole /= 2)//比父结点小,交换,交换到根结点,也就是1的时候,就要停止了
            {
                array[hole] = array[hole/2];//把父结点往下移动
            }
            array[hole] = x;//x放在最新的位置上面
        }
        //删除最小的一项
        void deleteMin()
        {
            if (isEmpty()) {
                throw "UnderflowException";//抛异常
            }
            array[1] = array[currentSize--];
            percolateDown(1);//进行下虑
        }
        //删除最小的一项
        void deleteMin(Comparable& minItem)
        {
            if (isEmpty()) {
                throw "UnderflowException";//抛异常
            }
            minItem = array[1];
            array[1] = array[currentSize--];
            percolateDown(1);//进行下虑
        }
        void makeEmpty()
        {
            currentSize = 0;
        }
    private:
        int currentSize;
        Vector<Comparable> array;
        //构建堆,主要应用在乱序的数据上面
        void buildHeap()
        {
            //大于currentSize/2的结点已经在最底层,是不需要下滤的了。
            for (int i = currentSize/2; i>0; i--)//必须从下往上进行下虑
            {
                percolateDown(i);
            }
        }
        //下虑,将不适合的对象往下沉到适合的位置,O(logN)
        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;//把对象放到孩子的位置。
        }
    };
}

#endif /* defined(__HelloWorld__Heap__) */

这是一般意义长的堆,因为用得最多。其实还有最大堆,根比子节点大。

STL实现了一个最大堆,而不是最小堆。

下面的堆概念平时比较少用到,以后要用到再研究了。

d堆:是二叉堆的简单推广,所有结点都有d个儿子。

查找儿子和父亲的乘法和除法都和因子d有关。

除非d是2的幂,否则将不能通过二进制移位来实现触发而导致运行时间急剧增加。

除了不能执行find操作外,两个堆合二为一是很困难的操作。

左式堆:以堆的形式构建,父节点比子节点小,不同的是,不是完全二叉树。

零路径长(null path length)npl(X)定义为从X结点到一个不具有两个儿子的节点的最短路径的长。

因此具有0或1个儿子的结点的npl为0.npl(NULL) == -1

斜堆(skew heap)是左式堆的自调节形式。

二项队列:一个二项队列不是一棵堆序的树,而是堆序的树的集合,称为森林。

作者:u012175089 发表于2017/1/10 22:35:03 原文链接
阅读:279 评论:0 查看评论
分类: 编程语言(其他) 标签: