Datawhale编程集训第三天
一、队列
1、简介
队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表，在具体应用中通常用链表或者数组来实现，队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作，队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
2、队列的操作
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
队列的另外一项重要操作是读取队头的元素。这个操作叫做peek()。该操作返回队头元素，但不把它从队列中删除。
Queue() 定义一个空队列，无参数，返回值是空队列。
enqueue(item) 在队列尾部加入一个数据项，参数是数据项，无返回值。
dequeue() 删除队列头部的数据项，不需要参数，返回值是被删除的数据，队列本身有变化。
isEmpty() 检测队列是否为空。无参数，返回布尔值。
size() 返回队列数据项的数量。无参数，返回一个整数。
队列操作代码：
# -*- coding:utf-8 -*-
class Queue():
#初始化队列
def __init__(self,size):
self.queue=[]
self.size=size
self.tail=0
#判断队列是否为满，为满返回True
def Full(self):
if self.tail==self.size:
return True
else:
return False
#判断队列是否为空，为空返回True
def Empty(self):
if self.tail==0:
return True
else:
return False
#进队
def queuein(self,content):
if self.Full():
print 'The queue is full!'
else:
self.queue.append(content)
self.tail+=1
#出队
def queueout(self):
if self.Empty():
print 'The queue is empty!'
return None
else:
content=self.queue[0]
self.queue.pop(0)
self.tail-=1
return content
#遍历队列
def queueall(self):
if self.Empty():
print 'The queue is empty!'
else:
for i in range(0,self.tail):
print self.queue[i]
二、堆排序
1、简介
堆排序是利用堆这种数据结构而设计的一种排序算法。堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
2、堆的特点
堆是完全二叉树，又分为大顶堆和小顶堆；大顶堆：每个结点的值都大于或等于其左右叶子结点的值；小顶堆：每个结点的值都小于或等于其左右叶子结点的值。
大根堆
小根堆
3、堆排序的主要思想：
将待排序列构造成一个大顶堆，此时堆顶元素就是整个序列的最大值，将堆顶元素与堆数组的末尾元素进行交换。然后将剩余的n-1个元素重新构造成一个堆，并得到整个序列的次大值。如此反复执行，得到一个有序的序列。
4、代码实现
#_*_coding:utf-8_*_
def sift_down(arr, node, end):
root = node
while True:
# 从root开始对最大堆调整
child = 2 * root +1 #left child
if child > end:
break
print("v:",root,arr[root],child,arr[child])
print(arr)
# 找出两个child中交大的一个
if child + 1 <= end and arr[child] < arr[child + 1]: #如果左边小于右边
child += 1 #设置右边为大
if arr[root] < arr[child]:
# 最大堆小于较大的child, 交换顺序
tmp = arr[root]
arr[root] = arr[child]
arr[child]= tmp
# 正在调整的节点设置为root
root = child
else:
# 无需调整的时候, 退出
break
print('-------------')
def heap_sort(arr):
# 从最后一个有子节点的孩子还是调整最大堆
first = len(arr) // 2 -1
for i in range(first, -1, -1):
sift_down(arr, i, len(arr) - 1)
#[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
print('--------end---',arr)
# 将最大的放到堆的最后一个, 堆-1, 继续调整排序
for end in range(len(arr) -1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(arr, 0, end - 1)
array = [16,9,21,13,4,11,3,22,8,7,15,29]
print(array)
heap_sort(array)
print(array)
三、Leetcode编程练习
题目：239 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。
思路：
- 每次入队如果新元素比队尾元素小，则将其删除，直至队尾元素大于新元素或队内无元素。（因为被删除元素既没有当前元素大，也没有当前元素新，所以肯定不会替代当前元素成为最大值的）
- 找最大值时从队头开始，如果队头元素对应的index不在当前窗口则将其删除，直到找到在窗口中的元素，即为最大值。
代码：
class Solution:
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if len(nums) == 0:
return []
if k == 0:
return nums
from collections import deque
deq = deque()
res = []
L = len(nums)
for i in range(L):
while deq and nums[i] > nums[deq[-1]]:
deq.pop()
deq.append(i)
if deq[0] < i - k + 1:
deq.popleft()
if i >= k - 1:
res.append(nums[deq[0]])
return res
运行结果：
参考内容：
https://blog.csdn.net/PKU_Jade/article/details/77934644
http://python.jobbole.com/85264/
https://www.cnblogs.com/linxiyue/p/3556875.html
http://blog.51cto.com/sevenot/2059588
http://python.jobbole.com/87577/
https://www.jianshu.com/p/d174f1862601
http://www.cnblogs.com/terry-c/p/9864994.html
https://www.cnblogs.com/NewsunLs/p/9568126.html
https://www.cnblogs.com/chengxiao/p/6129630.html
https://blog.csdn.net/dujiahaogod/article/details/79688331
