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

birdskyws

发布于 2018-09-12 15:49:10

6330

发布于 2018-09-12 15:49:10

文章被收录于专栏：一英里广度一英寸深度的学习一英里广度一英寸深度的学习

堆是什么鬼？

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

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

应用：多路快排

[引至第七城市])

最小堆

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

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

最小堆实现

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

操作方法：添加节点（上旋）

添加到树中最后一个节点位置，完全二叉树最后一个节点位置固定。
如果小于父亲节点，那么与父亲节点交换位置，直到没有父亲节点（根节点）。

操作方法：获取最小值（下旋）

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

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)

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.07.13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法