精华内容
参与话题
问答
  • 数据结构-(heap)与的Python实现

    千次阅读 2018-09-17 20:46:49
    数据结构-树介绍了什么是树,以及二叉树的实现。还记得树的三种特殊结构吗?完美二叉树,满二叉树和完全二叉树。这里介绍的结构就是一种完全二叉树。可分为最大和最小,区别就是父节点是否大于所有子节点。...

    <Python 算法与数据结构视频教程> 学习笔记

    1.什么是堆

    数据结构-树介绍了什么是树,以及二叉树的实现。还记得树的三种特殊结构吗?完美二叉树,满二叉树和完全二叉树。这里介绍的堆结构就是一种完全二叉树。堆可分为最大堆和最小堆,区别就是父节点是否大于所有子节点。最大堆的父节点大于它的子节点,而最小堆中子节点大于父节点。看图有个清晰的认识:



    2. 堆的表示

    堆可以使用list实现,就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系:

    parent = int((i-1) / 2)    # 取整
    left = 2 * i + 1
    right = 2 * i + 2
    

    其中i表示数组中的索引,如果left、right的值超出了数组的索引,则表示这个节点是不存在的。



    3.堆的操作

    (1)往堆中插入值,sift-up操作:



    往最大堆里添加一个元素,我们在使用数组实现的时候直接使用append()方法将值添加到数组的最后。这时候我们需要维持最大堆的特性,如下图。添加的新值90首先被放到堆的最后,然后与父节点的值作比较,如果比父节点值大,则交换位置。
    这里涉及到的问题是子节点与父节点之间的关系。

    # 堆中父节点i与子节点left、right的位置关系
    parent = int((i-1) / 2)    # 取整
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 已知子节点的位置j,求父节点的位置
    parent = int((j-1)/2)
    

    使用递归的方式,向上比较,直到根节点。

    (2)获取或删除根节点,sift-down操作;



    当我们把最大或者最小的值从堆中弹出,为了维持堆的特性,要使用sift-down操作。因为最大堆、最小堆的最值都在根节点,当弹出并返回根节点的值后,为了维持堆的特性,我们先将最后一个位置上的值放到根节点中。然后比较它与它的两个子节点中三个值的大小,选择最大的值放到父节点上。同理,我们这里也是使用递归的方式向下比较。这里涉及到两个问题:

    根据父节点确定子节点的位置:

    	# 父节点的位置,left,rigth为左右子节点的位置
        left = 2 * ndx + 1
        right = 2 * ndx + 2
    

    交换位置要满足几个条件条件,比如跟左子节点交换的条件:

    • 存在左子节点,
    • 左子节点大于右子节点,
    • 左子节点大于父节点

    4. 堆的实现

    使用Python实现堆结构,这里实现的是最大堆,里面用到了自己实现的数组,把它理解为list就行。
    因为在看一个视频教程,复制粘贴了一下老师的代码【这里】。

    最大堆

    class Array(object):
        """
        Achieve an Array by Python list
        """
        def __init__(self, size = 32):
            self._size = size
            self._items = [None] * size
    
        def __getitem__(self, index):
            """
            Get items
            :param index: get a value by index
            :return: value
            """
            return self._items[index]
    
        def __setitem__(self, index, value):
            """
            set item
            :param index: giving a index you want to teset
            :param value: the value you want to set
            :return:
            """
            self._items[index] = value
    
        def __len__(self):
            """
            :return: the length of array
            """
            return self._size
    
        def clear(self, value=None):
            """
            clear the Array
            :param value: set all value to None
            :return: None
            """
            for i in range(self._size):
                self._items[i] = value
    
        def __iter__(self):
            for item in self._items:
                yield item
                
    class MaxHeap(object):
        def __init__(self, maxsize=None):
            self.maxsize = maxsize
            self._elements = Array(maxsize)
            self._count = 0
    
        def __len__(self):
            return self._count
    
        def add(self, value):
            if self._count >= self.maxsize:
                raise Exception('full')
            self._elements[self._count] = value
            self._count += 1
            self._siftup(self._count-1)  # 维持堆的特性
    
        def _siftup(self, ndx):
            if ndx > 0:
                parent = int((ndx-1)/2)
                if self._elements[ndx] > self._elements[parent]:    # 如果插入的值大于 parent,一直交换
                    self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
                    self._siftup(parent)    # 递归
    
        def extract(self):
            if self._count <= 0:
                raise Exception('empty')
            value = self._elements[0]    # 保存 root 值
            self._count -= 1
            self._elements[0] = self._elements[self._count]    # 最右下的节点放到root后siftDown
            self._siftdown(0)    # 维持堆特性
            return value
    
        def _siftdown(self, ndx):
            left = 2 * ndx + 1
            right = 2 * ndx + 2
            # determine which node contains the larger value
            largest = ndx
            if (left < self._count and     # 有左孩子
                    self._elements[left] >= self._elements[largest] and
                    self._elements[left] >= self._elements[right]):  # 原书这个地方没写实际上找的未必是largest
                largest = left
            elif right < self._count and self._elements[right] >= self._elements[largest]:
                largest = right
            if largest != ndx:
                self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
                self._siftdown(largest)
    
    
    def test_maxheap():
        import random
        n = 5
        h = MaxHeap(n)
        for i in range(n):
            h.add(i)
        for i in reversed(range(n)):
            assert i == h.extract()
    

    最小堆

    class Array(object):
        """
        Achieve an Array by Python list
        """
        def __init__(self, size = 32):
            self._size = size
            self._items = [None] * size
    
        def __getitem__(self, index):
            """
            Get items
            :param index: get a value by index
            :return: value
            """
            return self._items[index]
    
        def __setitem__(self, index, value):
            """
            set item
            :param index: giving a index you want to teset
            :param value: the value you want to set
            :return:
            """
            self._items[index] = value
    
        def __len__(self):
            """
            :return: the length of array
            """
            return self._size
    
        def clear(self, value=None):
            """
            clear the Array
            :param value: set all value to None
            :return: None
            """
            for i in range(self._size):
                self._items[i] = value
    
        def __iter__(self):
            for item in self._items:
                yield item
    
    
    class MinHeap(object):
        """
        Achieve a minimum heap by Array
        """
    
        def __init__(self, maxsize = None):
            self.maxsize = maxsize
            self._elements = Array(maxsize)
            self._count = 0
    
        def __len__(self):
            return self._count
    
        def add(self, value):
            """
            Add an element to heap while keeping the attribute of heap unchanged.
            :param value: the value added to the heap
            :return: None
            """
            if self._count >= self.maxsize:
                raise Exception("The heap is full!")
            self._elements[self._count] = value
            self._count += 1
            self._siftup(self._count-1)
    
        def _siftup(self, index):
            """
            To keep the the attribute of heap unchanged while adding a new value.
            :param index: the index of value you want to swap
            :return: None
            """
            if index > 0:
                parent = int((index - 1) / 2)
                if self._elements[parent] > self._elements[index]:
                    self._elements[parent], self._elements[index] = self._elements[index], self._elements[parent]
                    self._siftup(parent)
    
        def extract(self):
            """
            pop and return the value of root
            :return: the value of root
            """
            if self._count <= 0:
                raise Exception('The heap is empty!')
            value = self._elements[0]
            self._count -= 1
            self._elements[0] = self._elements[self._count]
            self._siftdown(0)
            return value
    
        def _siftdown(self, index):
            """
            to keep the attribute of heap unchanged while pop out the root node.
            :param index: the index of value you want to swap
            :return: None
            """
            if index < self._count:
                left = 2 * index + 1
                right = 2 * index + 2
                if left < self._count and right < self._count \
                    and self._elements[left] <= self._elements[right] \
                    and self._elements[left] <= self._elements[index]:
                    self._elements[left], self._elements[index] = self._elements[index], self._elements[left]
                    self._siftdown(left)
                elif left < self._count and right < self._count \
                    and self._elements[left] >= self._elements[right] \
                    and self._elements[right] <= self._elements[index]:
                    self._elements[right], self._elements[index] = self._elements[index], self._elements[right]
                    self._siftdown(left)
    
                if left < self._count and right > self._count \
                    and self._elements[left] <= self._elements[index]:
                    self._elements[left], self._elements[index] = self._elements[index], self._elements[left]
                    self._siftdown(left)
    
    if __name__ == '__main__':
        import random
        n = 5
        h = MinHeap(n)
        for i in range(n):
            h.add(i)
        for i in range(n):
            assert i == h.extract()
    

    5. Python中的heapq模块

    这个模块提供了的堆是一个最小堆,索引值从0开始。而很多教材中都使用最大堆作为教学的例子,因为其排序是稳定的,而最小堆排序是不稳定的。
    Python中创建一个堆可以直接使用list的创建方式H = [], 或者使用heapify()函数将一个存在的列表转为堆。

    这个模块提供了下面几种堆的操作:
    heapq.heappush(heap, item)
    往堆中插入一个值,同时要保持为最小堆。

    heapq.heappop(heap)
    返回堆中的最小值,并把它从堆中删除,同时保持为最小堆;如果堆为空,发生 IndexError。直接通过heap[0]可以获取最小值并不从堆中把它删除。

    heapq.heappushpop(heap, item)
    向堆中插入值后再弹出堆中的最小值,这个函数的速度比直接使用heappush() 和heappop()的效率更加高。

    heapq.heapreplace(heap, item)
    弹出和返回堆中的最小值再插入一个新的值。堆的大小没有改变。如果堆为空,产生 IndexError。
    这一个操作也比直接使用heappush() 和heappop()的效率更加高,尤其适合使用在固定堆大小不变的情况。
    与上一个函数相比,这个函数返回的值可能要比将要插入到堆的值大。

    heapq.heapify(x)
    将一个list转为最小堆,线性时间复杂度,O(n).

    6.堆排序

    堆已经实现了,下面可以实现堆排序。


    Python 算法与数据结构视频教程

    展开全文
  • 数据结构》— 数据结构图文解析系列

    千次阅读 多人点赞 2017-08-11 11:54:52
    0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之:栈的简介及C++模板实现 ... 数据结构图文解析之:二叉详解及C++模板...

    查看原文点击链接即可

    0. 数据结构图文解析系列

    数据结构系列文章
    数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现
    数据结构图文解析之:栈的简介及C++模板实现
    数据结构图文解析之:队列详解与C++模板实现
    数据结构图文解析之:树的简介及二叉排序树C++模板实现.
    数据结构图文解析之:AVL树详解及C++模板实现
    数据结构图文解析之:二叉堆详解及C++模板实现
    数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现
    数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

    回到顶部

     

     

    数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

    阅读目录

     

    数据结构图文解析之:栈的简介及C++模板实现

    阅读目录

    数据结构图文解析之:队列详解与C++模板实现

    阅读目录

     

     

    数据结构图文解析之:树的简介及二叉排序树C++模板实现.

    阅读目录

    数据结构图文解析之:AVL树详解及C++模板实现

    阅读目录

    数据结构图文解析之:二叉堆详解及C++模板实现

    阅读目录

    数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

    阅读目录

     

    展开全文
  • 数据结构之Binary Heap(二叉

    千次阅读 2016-10-22 15:11:50
    数据结构之Binary Heap(二叉)1.Binary Heap的定义 二叉是一种特殊的,二叉是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉有两种:最大和最小。最大:父结点的键值总是大于或等于任何...

    数据结构之Binary Heap(二叉堆)

    1.Binary Heap的定义

    二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。二叉堆一般用数组来表示。例如,根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2。因此,第0个位置的子节点在1和2,1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。
    在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。 形式上看,它从顶点开始,每个节点有两个子节点,每个子节点又各自有自己的两个子节点;数值上看,每个节点的两个子节点都比它大或和它相等。

    2.Binary Heap的性质

    最小的元素在顶端(最大的元素在顶端),每个元素都比它的父节点小(大),或者和父节点相等。

    3.C语言数组实现Binary Heap

    /****************************************************
    Function:Binary Heap by using list
    Author:Robert.Tianyi
    Date:2016.11.22
    *****************************************************/
    #include<stdio.h>  
    #define MAX_N 50  
    int heap[MAX_N]; //堆数组 
    int sz = 0;  //当前堆大小 
    
    /*将元素X插入堆中pos位置*/ 
    void BiHeapExchange(int x,int pos){
        int temp;
        if(pos>sz){
            printf("\nBiHeapExchange() error!\n");
        }
        else{
            heap[pos]=x;
        }
    } 
    /*将元素X插入堆中*/ 
    void BiHeapInsert(int x)
    {  
        int now = sz++;//插入节点的位置  
        while(now > 0)  
        {  
            int f = (now - 1)/2;//父亲节点的编号  
            if(heap[f] <= x)break;//如果父亲节点数据大于当前元素则退出   
              heap[now] = heap[f];  
            now = f;   
        }  
        heap[now] = x;  
    } 
    /*从二叉堆中弹出优先级最高的值,即最小值*/  
    int BiHeapPop()  
    {  
        int res = heap[0];  
        int x = heap[--sz];//最末尾的节点   
        int i = 0;//从根节点开始操作   
        while(i * 2 + 1 < sz)  
        {  
            int lchild = 2 * i + 1;  
            int rchild = 2 * i + 2;  
            if(rchild < sz && heap[rchild] < heap[lchild])
                  lchild = rchild;  
            if(heap[lchild] >= x) break;//如果x已经在lchild上层了,就可以停止了   
            heap[i] = heap[lchild];  
            i = lchild;   
        }  
        heap[i] = x;  
        return res;  //放回最小值 
    }  
    int main()  
    {    
        int a[7]={10,45,1,2,3,4,5};
        int i;
        printf("需要压进堆的数据:\n");
        for(i=0;i<7;i++)
            printf("%3d",a[i]);
        for(i=0;i<7;i++){
            BiHeapInsert(a[i]);
        }
        printf("\n堆数据:\n");
        for(i=0;i<7;i++){
            printf("%3d",heap[i]);
        }
        printf("\n66与3号位置元素交换:\n");
        printf("\n输出当前堆,堆数据:\n");
        BiHeapExchange(66,3);
        for(i=0;i<7;i++){
            printf("%3d",heap[i]);
        }
        printf("\n从堆中删除元素\n");
        for(i=0;i<7;i++)
           printf("当前堆size:%d  pop=%d  \n",sz+1,BiHeapPop());  
        return 0;  
    }

    运行结果如下:
    这里写图片描述

    展开全文
  • 数据结构-(Heap)

    万次阅读 多人点赞 2018-08-18 21:50:05
    数据结构-(Heap) 我认识的: 1.建立在完全二叉树的基础上 2.排序算法的一种,也是稳定效率最高的一种 3.可用于实现STL中的优先队列(priority_queue)  优先队列:一种特殊的队列,队列中元素出栈的顺序...
    • 数据结构-堆(Heap)


    • 我认识的堆:

    1.建立在完全二叉树的基础上

    2.排序算法的一种,也是稳定效率最高的一种

    3.可用于实现STL中的优先队列(priority_queue)

     优先队列:一种特殊的队列,队列中元素出栈的顺序是按照元素的优先权大小,而不是元素入队的先后顺序

    4.两类:

          a.最大堆:

               ①根的值大于左右子树的值   ②子树也是最大堆

           b.最小堆:

               ①根的值小于左右子树的值   ②子树也是最小堆

     

    堆的实现:

    堆一般用数组表示

    1.插入(Insert):

    以最大堆为栗子,插入其实就是把插入结点放在堆最后面,然后与父亲比较,如果父亲值小于它,那么它就和父亲结点交换位置,重复该过程,直到插入节点遇到一个值比它大的父亲或者它成为树根结点

    以最大堆为栗子,在堆中插入值为20的结点(红色结点代表新进入)

     

    20明显大于它的父亲结点值,所以和7交换位置,交换后新的父亲值还是比它小,继续交换

     一步一步与它前面比它小的父亲结点交换位置,最后20成为根结点

    最小堆同理,只不过要求父亲结点要比它小,如果父亲结点大于它,就得交换

    2.删除(Pop):

    删除就是删除最大堆中的最大值或者最小堆中的最小值,也就是树根

    以删除最大堆树根为例子,删除其实就是整个堆中少了一个结点,不妨把位于最后面的一个结点当成新的树根,然后与它左右孩子比较,与值最大并且值大于它的孩子进行交换(好好读这句话),直到它的孩子都是小于它的,或者变成树叶

    还是用最大堆为例,删除树根20

    把最后的结点8提到树根

    然后就按说明步骤,找到一个位置,它的孩子都小于它或者他变成树叶

    • 堆模板代码:

    //最小堆
    #define MAX_SIZE 100005
    int Heap[MAX_SIZE];
    int Cur = 0;
    
    void Insert(int val)     //插入
    {
    	Heap[++Cur] = val;     //新元素加入堆
    	int Temp_Cur = Cur;
    	while (Temp_Cur > 1)   //新元素还没成为树根时
    	{
    		int Root = Temp_Cur / 2;   //找爸爸
    		if (Heap[Root] > val)    //爸爸比它大
    			swap(Heap[Root], Heap[Temp_Cur]);  //交换
    		else
    			break;    //它已经在堆中立足
    		Temp_Cur = Root;     //该新结点的新位置
    	}
    }
    
    int Pop()    //删除
    {
    	if (Cur == 0)  //堆空
    		return -99999999;
    	int Temp_Top = Heap[1];   //保存堆顶
    	Heap[1] = Heap[Cur];   //将末尾结点提到树根
    	int Root = 1;   
    	while (2 * Root < Cur)   //还没有变成树叶
    	{
    		int L_Child = Root * 2;   //左儿子
    		int R_Child = Root * 2 + 1;   //右儿子
    		if (R_Child >= Cur || Heap[L_Child] < Heap[R_Child])  //没有右儿子或者左儿子值小
    		{
    			if (Heap[Root] > Heap[L_Child])  //比最小的儿子大
    			{
    				swap(Heap[Root], Heap[L_Child]);  //交换
    				Root = L_Child;  //新位置
    			}
    			else
    				break;
    		}
    		else
    		{
    			if (Heap[Root] > Heap[R_Child])  
    			{
    				swap(Heap[Root], Heap[R_Child]);
    				Root = R_Child;
    			}
    			else
    				break;
    		}
    	}
    	Cur--;
    	return Temp_Top;  //返回堆顶
    }
    • 堆的用途:

    高效排序:

    对于许多acm题目来说超时很简单,所以一般能不用sort就别用,堆排序很快,在排序类,贪心类题目中会用到,不过不用自己写,STL中的queue提供了堆的模板--优先队列(priority_queue)

    实现Huffman:

    哈夫曼算法在构建哈夫曼树时每次必须把结点排序取最小的两个结点构建子树,这很好的用到了堆,还是因为快,自己上个月写了哈夫曼树的一篇blog用了sort,而且把Huffman树存在数组。。。好像是为了方便后面编码,到时候用优先队列和链表试着更新。

    Huffman基础可以先了解: 数据结构-哈夫曼树(Huffman)

    • 图片来源:

    热情de马金-数据结构之堆(Heap)及其用途

    展开全文
  • 数据结构 Heap

    2013-12-04 15:11:43
    (Heap) - 也叫做优先队列(Priority Queue);二叉是一个完全二叉树或近似完全二叉树。满足如下的两个属性: 1 父节点的键值总是大于或等于(小于或等于)它的任意一个子节点的键值(顺序性); 2 总是一个完全二叉树...
  • 的定义 n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为。 情形1:ki 2i 且ki 2i+1 (最小化... 若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,
  • 数据结构-heap

    万次阅读 2016-05-15 20:00:44
    heap)也被称为优先队列(priority queue)。队列中允许的操作是先进先出(FIFO),在队尾插入元素,在队头取出元素。而也是一样,在底插入元素,在顶取出元素,但是中元素的排列不是按照到来的先后顺序...
  • 数据结构-- Heap

    2019-05-30 00:52:02
    是一种特殊的树 a. 是完全二叉树(除最后一层,其他层都是满的,最后一层节点都靠左) b. 没一个节点都大于等于(或者都小于等于)其子树中每个节点的值 2. 操作和存储 完全二叉树适合用数组存储,节省空间...
  • 数据结构 - 排序(heap sort) 详解 及 代码(C++)

    千次阅读 多人点赞 2014-06-16 11:10:16
    排序(heap sort) 详解 及 代码(C++) 本文地址:http://blog.csdn.net/caroline_wendy 排序包含两个步骤: 第一步:是建立大顶堆(从大到小排序)或小顶堆(从小到大排序), 从下往上建立; 如建时, s是从大到小...
  • 基本概念: ...(英语:heap)是计算机科学中一类特殊的数据结构的统称。通常是一个可以被看做一棵树的数组对象。总是满足下列性质: 中某个节点的值总是不大于或不小于其父节点的值; ...
  • 该模块提供了队列算法的实现, 也称为优先级队列算法。是二叉树, 每个父节点的值都小于或等于其任何子节点,它最小的元素始终是根。 部分函数说明: heapq.heapify(x):在线性时间内将列表x转换为。 heapq....
  • 数据结构heap

    千次阅读 2013-12-29 19:44:09
    是一种完全二叉树(complete binary tree);若其高度为h,则1~h-1层都是满的。下图[1]给出了完全二叉树、非完全二叉树: 从左至右从上至下,从1开始给节点编号。满二叉树满足: (a)节点i的父节点编号为i/2 (b)...
  • 排序是利用这种数据结构所设计的排序算法,是一种近似于完全二叉树。分为大顶堆和小顶堆。时间复杂度为:o(nlog2(n)),不稳定。 算法描述: 知识储备:一般都用数组来表示,i结点的父结点下标就为(i – 1) / ...
  • 初入数据结构(Heap)以及Java实现 的常用场景: 构建优先队列 支持排序 快速找出一个集合中的最小值(或者最大值) 比如我们要实现一个优先队列的时候,通常会以下几种底层数据结构 数据...
  • 数据结构(Heap)及其用途

    千次阅读 2016-12-07 18:57:16
    图、码、文 介绍 优先队列之 优先队列;最大树;最大、最小的插入、删除、初始化; 的用途:排序;haffman编码;haffman tree 解决优化问题
  • 是一种经过排序的树形数据结构,每个节点都有一个值,通常我们所说的数据结构是指二叉树。所以数据结构中通常可以被看做是一棵树的数组对象。而且需要满足一下两个性质: (1)中某个...
  • 数据结构Heap)的实现

    千次阅读 2016-05-24 15:28:10
    堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构,所以也叫做二叉。二叉满足二个特性: 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。 2.每个结点的左子树和右子树都是一...
  • 提出这样一个问题: 输入一个序列a[1..n]进行m次操作 ·操作1:将x插入到数列中 ·操作2:输出最小值 ·操作3:将最小值删除 (n,m 先尝试按照普及组的思路...很显然线性结构已经不满足这道题目的要求,然而我们可以用(he

空空如也

1 2 3 4 5 ... 20
收藏数 73,024
精华内容 29,209
关键字:

heap