【数据结构2】Queue & Stack & heapq

2018年07月01日

Author: Guofei

文章归类: 8-数据结构与算法，文章编号: 502

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2018/07/01/queue_stack.html

Edit

主要内容

stack
queue：一种 first-in-first-out (FIFO) 算法
优先队列、优先堆：Last-in-first-out Data Structure（先进先出表）
多级反馈队列

栈

队列

Circular Queue

用list来模拟Cirular Queue

num_list[i%len_list]

二叉堆

扩展阅读

二叉堆是一种特殊的堆。具有如下的特性：

具有完全二叉树的特性。
堆中的任何一个父节点的值都大于等于它左右孩子节点的值，或者都小于等于它左右孩子节点的值。借此，又可以把二叉堆分成两类：
1. 最大堆：父节点的值大于等于左右孩子节点的值。
2. 最小堆：父节点的值小于等于左右孩子节点的值。

二叉树往往用一维链表来实现，二叉堆却可以用顺序表来实现。 这是因为，根据完全二叉树的特点，假如一个节点的下标为n,则可以求得它左孩子的下标为：2n+1；右孩子下标为：2n+2

下面看看二叉堆的三个基本操作（以最小堆为例）：

插入一个节点。
删除一个节点。
构建一个二叉堆。

插入一个节点的算法流程如下：

把新节点放到二叉堆的末尾
调整二叉堆，使其满足二叉堆的性质。调整策略：让新插入的节点与它的父节点进行比较，如果新节点小于父节点，则让新节点上浮（上浮换句话说，是和父节点交换位置），不断上浮，直到新节点不小于父节点。

删除一个节点的算法流程如下：

把跟节点删掉，把二叉堆末尾拿出来，放到跟节点位置
调整二叉堆，使其满足二叉堆的性质。调整策略是，跟节点与孩子节点比较，不断下沉

构建一个二叉堆的算法流程如下：

首先是面临一个无序的完全二叉树
从最下方开始，遍历每一个节点，使其下沉。（当然，叶节点不能下沉，也就无需遍历了）

TODO，这里需要添加一个Python实现，另外，还有一个Python库已经有了，如下：

heapq是一种特殊的二叉树，这种二叉树中，任何父节点都不大于子节点。
也就是说，heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] for all k

heapq

heapq 模块提供堆算法，官方文档

import heapq
heap=[] # 创建一个空的 heap
heapq.heapify(<list>) # 把list转化为 heapq，时间复杂度为O(n)

heapq.heappush(heap, item) # 插入一个新值
heapq.heappop(heap) # 返回并删除最小的值（也就是树最顶端的值）

heapq.heappushpop(heap, item)
# 相当于做这个(但速度更快)：
# heapq.heappush(heap,item);heapq.pop()
heapq.heapreplace(heap, item)
# 相当于做这个(但速度更快)：
# heapq.pop();heapq.heappush(heap,item)

应用

[heapq.pop(heap) for i in range(len(heap))] # 等价于 sorted

heap=[]
for i in [4,3,2,5,6]:
    heapq.heappush(heap,[1,i]) # 注意到list和str也可以比大小，所以 item 可以是 list, str

show_tree

（这个函数来自网络）
这个是自编函数，功能是打印heap
可以输入list，也可以输入heap

import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor((total_width * 1.0) / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)
    print
    return

应用示例1:show_tree

（输入可以是list，也可以是heap）

data = range(1, 8)
print('data: ', data)
show_tree(data)

output

data:  range(1, 8)

                 1                  
        2                 3         
    4        5        6        7    
------------------------------------

应用示例2：heapify

heapify可以在线性时间内进行排序
需要注意，直接改输入的list，而不是return一个list

import random
import heapq
heap = random.sample(range(1, 8), 7)
heapq.heapify(heap)
show_tree(heap)

output


                 7                  
        3                 5         
    1        2        4        6    
------------------------------------

                 1                  
        2                 4         
    3        7        5        6    
------------------------------------

应用示例3：heappush

下面展示多次heappush的过程：

import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor((total_width * 1.0) / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)
    print
    return

import heapq
import random

heap = []
data = random.sample(range(1, 8), 7)
print('data:', data)
for i in data:
    heapq.heappush(heap, i)
    show_tree(heap)

output：

data: [1, 4, 7, 6, 2, 5, 3]

                 1                  
------------------------------------

                 1                  
        4         
------------------------------------

                 1                  
        4                 7         
------------------------------------

                 1                  
        4                 7         
    6    
------------------------------------

                 1                  
        2                 7         
    6        4    
------------------------------------

                 1                  
        2                 5         
    6        4        7    
------------------------------------

                 1                  
        2                 3         
    6        4        7        5    
------------------------------------

应用示例4：heappop

import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor((total_width * 1.0) / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)
    print
    return

import heapq
import random

data = random.sample(range(1, 8), 7)
print ('data: ', data)
heapq.heapify(data)
show_tree(data)

heap = []
while data:
    i = heapq.heappop(data)
    print('pop %3d:' % i)
    show_tree(data)
    heap.append(i)
print('heap: ', heap)

list实现栈和队列

我们知道，list天然地适合做 Stack，即尾部入，尾部出。
我们又知道 list 删除头部的元素是极为低效的，解决方法是很简单，只要增加一个指向头部的指针即可，。

TODO：这里还需要补充

应用

queue 案例1

queue的一种典型应用场景是Breadth-first Search (BFS)

queue 案例2

题目灵感来自LeetCode题目,我给出的解答见于这里

input_queue=[1,2,3,4,5]    
stack=[2,1]
pointer=0
for i in input_queue:
    stack.append(i)
    # 后两行是先出的功能：
    stack_out=stack[pointer]
    pointer+=1

# 事实上，因为可以使用stack[-1],stack[-2]这些命令，所以 pointer 这个变量往往不必定义
# 会有内存浪费，定期清理即可，参考代码： stack=stack[pointer:]

案例1

深度优先搜索 Depth-First Search (DFS)

案例

200. Number of Islands

您的支持将鼓励我继续创作！

【数据结构2】Queue & Stack & heapq