专栏首页光城(guangcity)如醉如痴之最小堆

如醉如痴之最小堆

如醉如痴之最小堆

0.说在前面1.问题2.思考3.自虐4.回归5.总结6.作者的话

0.说在前面

一道简单的题,可以让你如醉如痴,更是因为这一道题,你才会学会很多,不要小看简单,简单中蕴含深意。

昨天碰到一道题,题目很简单,也是一个简单题,但是不导入库,实现起来就没那么简单了。。

当时一直在想,不要库怎么实现,就来学习堆的原理,然后去参考网上资料,开始动手实现了。

来个顺口溜:栈不是堆,堆不是栈,栈是堆栈,堆栈是栈,堆不是堆栈

你晕了没,是不是有点绕~~

我们一起来看一下这道简单题,通过最小堆来实现。

由于这次问题,中文网站上没有,所有就在英文网站上。英文弱的克服一下,后面来大概说明一下意思。

1.问题

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer kand an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note: You may assume that nums' length ≥ k-1 and k ≥ 1.

首先声明一个数组,然后给定一个k,寻找前k个数的最小值,比如[4,5,8,2]中,前三个数为4 5 8,最小为4,当后面的数比这个4大的时候就替换掉4,然后重新排序,选取三个中最小的,依此往后进行。

看到这个问题,对应的数据结构为堆排序中的最小堆!

实际就是利用最小堆去解决Top-k问题。

2.思考

这道题,先来一个简单的思路,通过导入库来实现。

这里要学习的库是heapq

这里用到的方法介绍:

heapq.heappush(heap, item) 把item添加到heap中(heap是一个列表)
heapq.heappop(heap) 删除堆顶元素,返回删除后的堆
heapq.heappushpop(heap, item) 先把item加入到堆中,然后再pop,比heappush()再heappop()要快得多
heapq.heapify(x) 将列表x进行堆调整,默认的是小顶堆

下面是参考的leetcode英文网站的discuss上面的两个实现思路:

思路1

对现有的数组堆进行调整,然后切割成两个list,第一个用来存储前k个元素所组成的堆,后一个用来存储其余元素,然后遍历一个list,从中找出大于第一个中最小的元素,然后通过heapq.heappushpop()方法,实现入堆,删除堆中最小元素,然后调整即可!

class KthLargest(object):
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums[:k]
        heapq.heapify(self.heap)
        rest = nums[k:]
        for num in rest:
            if num < self.heap[0]:
                continue
            heapq.heappushpop(self.heap, num)
    def add(self, val):
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heappushpop(self.heap, val)
        return self.heap[0]

思路2

这个思路跟前面差不多,区别在于前面的构造方法里面调用的函数不一样,下面这个比前面要稍微优一点,主要体现在,没有处理list分割,直接不断筛选出最后的堆,然后添加元素,选择即可!

class KthLargest(object): 
    def __init__(self, k, nums):
        self.pool = nums
        self.k = k
        heapq.heapify(self.pool)
        while len(self.pool) > k:
            heapq.heappop(self.pool)
    def add(self, val):
        if len(self.pool) < self.k:
            heapq.heappush(self.pool, val)
        elif val > self.pool[0]:
            heapq.heapreplace(self.pool, val)
        return self.pool[0]

3.自虐

上面提到的方法,我感觉有点不真实。。竟然leetcode可以调第三方库,好吧。其实,我之前就知道可以调库,但是对于这道题我当时的思路是没有往调库方面想,就开始自虐模式,自己实现了一个heapq

接下来,让我们一起来从最小堆理论分析,到最小堆实现过程。。

实现的方法有:

updateHeap()  # 调整堆
heapify()     # 创建堆同时调整堆
heappushpop() # 先把item加入到堆中,然后再pop,在调整堆
heappop()     # 删除堆顶元素,返回删除后的堆

目的很简单,就是不用heapq,自己去实现heapq,然后再按照上面说的思路完成本题。

数据结构定义

这里初始化heapList,将第一个元素设为0,目的有两个,第一来防止为空,第二便于后面堆的调整

def __init__(self):
    self.heapList = [0]
    self.currentSize = 0

首先,随便给我们一个list或者array,我们需要建堆,那么这个建堆有点像调整堆。所以这里我将建堆与调整堆,封装在一块!

堆调整

堆怎么调整呢?

一个最小堆满足完全二叉树性质!

最小堆满足的特点是:比左右子节点都小,并且当前节点位置如果为i,则左子节点为2i,右子节点为2i+1

注意一点,这里写的是自顶向下的堆调整!

思路就是判断当前节点是否有子节点,如果没有不更新,有则更新。

更新操作:判断是否有右子节点,如果没有,则直接返回左自己点,随后比较当前节点与左子节点的大小即可,然后根据谁大谁小进行交换即可。

如果有右子节点,就比较麻烦了,得先判断是左子节点小,还是右子节点小,如果是左子节点,然后设定最小的节点,将当前节点与最小子节点比较,根据情况交换子节点与当前节点即可。

def updateHeap(self, i):
    while (i * 2) <= self.currentSize:
        # 堆调整
        if i * 2 + 1 > self.currentSize:
            j =  i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                j = i * 2
            else:
                j = i * 2 + 1
        if self.heapList[i] > self.heapList[j]:
            tmp = self.heapList[i]
            self.heapList[i] = self.heapList[j]
            self.heapList[j] = tmp
        i = j

建堆

从树中间开始,然后回溯到根节点,用updateHeap方法使得最大子节点下沉!

    def heapify(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.updateHeap(i)
            i = i - 1
        return self.heapList

入堆出堆合并

先把val加入到堆中,然后再remove掉堆顶元素,再生成新堆即可!

def heappushpop(self, val):
    self.heapList.append(val)
    self.currentSize += 1
    print(self.heapList)
    # 删除堆顶元素
    self.heapList.remove(self.heapList[1])、
    # 删除堆list前面的0元素
    self.heapList.remove(self.heapList[0])
    self.heapList = self.heapify(self.heapList)
    self.currentSize -= 1
    return self.heapList

入堆

这里主要是list操作,记得将开头的0号元素删除掉即可!

def heappush(self, val):
    self.heapList.append(val)
    self.currentSize += 1
    self.heapList.remove(self.heapList[0])
    self.heapList = self.heapify(self.heapList)
    return self.heapList

出堆

直接出堆,0号元素是初始化的默认值,1号元素刚好是最小堆堆顶!

def heappop(self):
    # self.heapify(self.heapList)
    self.heapList.remove(self.heapList[1])
    self.currentSize-=1
    return self.heapList

4.回归

自虐模式完毕后,开始下一步的操作,那就是模仿上述实现本题。

上述的方法都是直接封装在这个类中,然后通过self调用!

思路1实现:

class KthLargest(object):
    def __init__(self, k, nums):
        self.heapList = [0]
        self.currentSize = 0
        self.k = k
        l = nums[:k]
        self.heapList = self.heapify(l)
        for num in rest:
            if num < self.heapList[1]:
                continue
            self.heapList=self.heappushpop(num)
    def add(self, val):
        if len(self.heapList)-1 < self.k:
            self.heapList = self.heappush(val)
        elif val > self.heapList[1]:
            self.heapList=self.heappushpop(val)
        return self.heapList[1]

思路2实现:

class KthLargest(object):
    def __init__(self, k, nums):
        self.heapList = [0]
        self.currentSize = 0
        self.k = k
        self.heap = nums
        self.heapList = self.heapify(self.heap)
        while len(self.heapList)-1 > self.k:
            self.heapList = self.heappop()
    def add(self, val):
        print(len(self.heapList))
        if len(self.heapList)-1 < self.k:
            self.heapList = self.heappush(val)
        elif val > self.heapList[1]:
            self.heapList=self.heappushpop(val)
        return self.heapList[1]

参考文章: http://python.jobbole.com/85338/#article-comment

5.总结

对于这些数据结构,在考试的时候,笔试题万一考到,让你手写二叉树,堆排序实现,那在考场上直接写,有点伤,那么就得线下多多练习。

虽然这里实现了,但是遗憾的是提交到leetcode上超时,共10个用例,最后一个没通过,原因你懂的,超时了~~。下次用二叉排序实现一下。应该要好点。

一道简单的题,可以让你如醉如痴,更是因为这一道题,你才会学会很多,不要小看简单,简单中蕴含深意。

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1.8亿条海量Txt数据存储MySQL实践

    最近出去旅游了,嗨皮了嗨皮,明天上班,开始做作业,今日将1.8亿数据存储的方式进行总结,欢迎大家拍砖!

    公众号guangcity
  • 揭开神秘的面纱

    打开f12检查页面后,刷新一下页面,点击Network,再点击下面的XHR,查看动态数据,会发现如下图所示,有两行数据。

    公众号guangcity
  • 第二期编程实践之快乐数

    0.导语1.快乐数1.0 问题1.1 递归+哈希+循环1.2 非递归+哈希+循环1.3 循环替代1.4 哈希表替代1.5 数字4的作用2.作者的话

    公众号guangcity
  • Python面向对象(成员)(二)

            特点: 在声明的时候. 需要给出self, self必须放在第一个位置

    py3study
  • 利用Python编写一个行业专用的小计算器

    前言:本文讲述的是如何利用python编程制作一个适用于指定行业的计算器,方便计算结果,涵盖的知识点由Python编写GUI界面程序,利用爬虫采集实时的汇率数据...

    用户7886150
  • python的tkinter编程(九)Text多行文本框的详细解读

    一天不写程序难受
  • PyQt 编程入门(六.3)

    from PyQt5.QtCore import QTimer from PyQt5.QtWidgets import * import sys

    用户6021899
  • python的tkinter编程(八)Entry组件的详细介绍,以登录界面作为讲解

    写一个按钮,绑定一个方法,当点击这个按钮的时候,就会执行这个方法,在这个方法里面 获取到对应的你输入的值,将获取到的值传到数据库里面进行比对,失败给一个返回的...

    一天不写程序难受
  • PyQt5 非模态对话框(live 型)

    本篇介绍非模态“实时”(live)对话框。与上一篇讲的”apply型“非模态对话框的区别是,非模态“实时”(live)对话框没有任何按钮,且所做的任何改变会自动...

    用户6021899
  • PyQt5 对话框 数据验证

    本篇介绍PyQt5对话框的数据合法性的验证。有两种验证方式:预防式验证(preventative)和 提交后验证 (post-mortem)。预防式验证适合于单...

    用户6021899

扫码关注云+社区

领取腾讯云代金券