一秆乳、隊列
1缀程、簡介
隊列（queue）诲泌，是先進先出（FIFO, First-In-First-Out）的線性表，在具體應用中通常用鏈表或者數組來實現伸眶，隊列只允許在后端（稱為rear）進行插入操作惊窖，在前端（稱為front）進行刪除操作，隊列的操作方式和堆棧類似厘贼，唯一的區(qū)別在于隊列只允許新數據在后端進行添加界酒。
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)陷虎，它也是不穩(wěn)定排序到踏。
堆排序是一種選擇排序，整體主要由構建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成尚猿。其中構建初始堆經推導復雜度為O(n)窝稿，在交換并重建堆的過程中，需交換n-1次凿掂，而重建堆的過程中伴榔，根據完全二叉樹的性質，[log2(n-1),log2(n-2)...1]逐步遞減庄萎，近似為nlogn踪少。所以堆排序時間復雜度一般認為就是O(nlogn)級。
2糠涛、堆的特點
堆是完全二叉樹援奢，又分為大頂堆和小頂堆；大頂堆：每個結點的值都大于或等于其左右葉子結點的值忍捡；小頂堆：每個結點的值都小于或等于其左右葉子結點的值集漾。
3切黔、堆排序的主要思想：
將待排序列構造成一個大頂堆，此時堆頂元素就是整個序列的最大值具篇，將堆頂元素與堆數組的末尾元素進行交換纬霞。然后將剩余的n-1個元素重新構造成一個堆，并得到整個序列的次大值驱显。如此反復執(zhí)行诗芜，得到一個有序的序列。
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
# 正在調整的節(jié)點設置為root
root = child
else:
# 無需調整的時候, 退出
break
print('-------------')
def heap_sort(arr):
# 從最后一個有子節(jié)點的孩子還是調整最大堆
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, 繼續(xù)調整排序
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/
http://www.reibang.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
