开发者社区> 白头雁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

线性排序算法-堆排序 (2)

简介: 堆是什么鬼? 在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。
+关注继续查看

堆是什么鬼?

在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

但是堆结构和栈结构不同,栈结构不关心除栈顶之外的元素,而整个堆是有结构的。本文介绍一种最小堆,利用完全二叉树结构实现。

应用:多路快排

[引至第七城市])

最小堆

首先介绍另一个概念,优先队列。元素添加到队列之后,按照元素的大小顺序,小的元素先出队列。

朴素思想是采用快速排序,选最小的。那么,出队复杂度O(1),入队复杂度二分查找O(logn)。但每次插入,都需要移动O(n)的元素。

最小堆实现

  1. 完全二叉树
  2. 父节点小于他的子节点

操作方法:添加节点(上旋)

  1. 添加到树中最后一个节点位置,完全二叉树最后一个节点位置固定。
  2. 如果小于父亲节点,那么与父亲节点交换位置,直到没有父亲节点(根节点)。

操作方法:获取最小值(下旋)

  1. 堆顶元素(二叉树的根节点)即是最小值,
  2. 将二叉树的最后一个节点放到根节点上,如果该节点小于子节点,与子节点交换,直至没有子节点。两个子节点,选择最小的子节点替换。

Python代码

利用列表List实现堆、完全二叉树,可以参考第一张图,形象化理解。

class MiniHeap(object):
    
    def __init__(self):
        self.heap = []
        self.count = 0
    def swap(self,i,j):
        tmp = self.heap[i]
        self.heap[i] = self.heap[j]
        self.heap[j] = tmp
    
    def swapUp(self,index):
        while(index>0):
            parent = (index-1)//2
            if(self.heap[parent] > self.heap[index] ):
                self.swap(parent,index)
                index = parent
            else:
                break
            
    def swapDown(self,index):
        lchild = index*2+1 # 左孩子的序号
        while lchild<self.count :# 左孩子存在
            rchild = lchild+1
            if(rchild<self.count and self.heap[rchild] < self.heap[lchild] and self.heap[rchild] < self.heap[index]  ):
                self.swap(index,rchild)
                index = rchild
                lchild = index*2+1
            elif(self.heap[lchild]<self.heap[index]):
                self.swap(index,lchild)
                index = lchild
                lchild = index*2+1
            else:
                break
                    
    def pop(self):
        assert(self.count>0)
        ret = self.heap[0]
        self.count = self.count-1
        if(self.count > 0):
            self.heap[0] = self.heap[self.count]
            self.swapDown(0)
        self.heap.pop()
        return ret
    def top(self):
        assert(self.count>0)
        return self.heap[0]
    def insert(self,item):
        self.heap.append(item)
        self.count = self.count+1
        self.swapUp(self.count-1)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法-基数排序和堆排序
排序算法-基数排序和堆排序
24 0
算法渣-排序-堆排序
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
19 0
八大排序算法~堆排序
八大排序算法~堆排序
49 0
排序算法(二):选择排序
选择排序算法维护一个待排序集合和一个已排序集合,每轮迭代,从待排序集合中选择一个最小(最大)元素,添加到已排序集合中,通过多次迭代,最终完成排序。
743 0
算法 - 排序 - 选择排序
每次循环把最小的值往前移 C++代码: Sorter.hpp #ifndef _Algorithm_Sorter_H_ #define _Algorithm_Sorter_H_ template class Sorter { public: static void...
754 0
堆排序算法---属于选择排序
1.堆   堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:   Key[i]=key[2i+2]   即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。   堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Ke...
572 0
排序算法系列
概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。
1019 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载