复杂数据结构

堆

• 堆是一个二叉树，其中每个父节点的值都小于等于其所有子节点的值。
• 数组heap[k]<=heap[2*k+1]
• 列表heap[k]<=heap[2*k+2]
• 整个堆中最小的元素总是位于二叉树的根节点
• Python中提供了heap模块提供相应的支持

import heapq
import random
data = list(range(10))
random.shuffle(data)
data

heap = []
# 建堆
for n in data:heapq.heappush(heap,n) #参数1，被插入的堆变量，参数2，插入的值
heap

[0, 1, 2, 4, 6, 7, 3, 9, 5, 8]

heapq.heappush(heap,0.5)
heap

[0, 0.5, 2, 4, 1, 7, 3, 9, 5, 8, 6]

heapq.heappop(heap) #弹出最小的元素，即根节点元素，堆会自动重建
heap

[0.5, 1, 2, 4, 6, 7, 3, 9, 5, 8]

myheap = [1,2,3,4,5,7,9,0,10,333]
#将列表转化为堆
heapq.heapify(mylist)
myheap 

[1, 2, 3, 4, 5, 7, 9, 0, 10, 333]

heapq.heapreplace(myheap,333) #替换堆中元素值，自动重构堆
myheap

[3, 4, 7, 0, 5, 333, 9, 1, 10, 333]

max_value = (a,b,c) =heapq.nlargest(3,myheap) #返回前3个最大的元素
max_value

[333, 333, 10]

min_value = (a,b) = heapq.nsmallest(2,myheap) # 返回前2个最小的元素
min_value

[0, 1]

队列

• 队列的特点：FIFO(先进先出) LILO(后进后出)
• 应用场景：
  • 多线程编程
  • 作业处理
  • 流式编程
  • Rest风格
• Python提供了queue模块和collections.deque模块支持队列的操作

import queue
q = queue.Queue() # 创建队列对象
q.put(0)  # 向队列中插入数据
q.put(1) 
q.put(2)
q.queue

<queue.Queue at 0x23a656ea688>

q.get()  # 队列头元素出队

0

q.queue

deque([1, 2])

q.get()

1

q.queue

deque([2])

后进先出队列

import queue
LiFoQueue = queue.LifoQueue(5)  # 后进先出队列的对象创建
LiFoQueue.put(1)
LiFoQueue.put(2)
LiFoQueue.put(3)
LiFoQueue.get()

3

LiFoQueue.get()

2

LiFoQueue.get()

1

优先级队列

import queue
PriQueue = queue.PriorityQueue(5) #创建优先级队列对象
PriQueue.put(3)
PriQueue.put(5)
PriQueue.put(1)
PriQueue.put(8)

PriQueue.queue

[1, 5, 3, 8]

PriQueue.get()

1

PriQueue.get()

3

PriQueue.get()

5

PriQueue.get()

8

自定义队列结构

class myQueue:#构造函数，默认队列大小为10def __init__(self,size =10):self._content = [ ]self._size = sizeself._current = 0def setSize(self,size):if size<self._current:#如果缩小队列，应删除后面的元素for i in range(size,self._current)[::-1]:del self._content[i]self._size=sizeself._size = sizedef put(self,v):if self._current<self._size:self._content.append(v)self._current = self._current + 1else:print('The queue is full')def get(self):if self._content:self._current = self._current -1return self._content.pop(0)else:print('This queue is empty!')def show(self):if self._content:print(self._content)else:print("This queue is empty!")def clear(self):self._content= [ ]def isEmpty(self):if not self._content:return Trueelse:return Falsedef isFull(self):if self._current == self._size:return Trueelse:return Falseif __name__ == '__main___':print('Please use me as a module.')

自定义二叉树

class BinaryTree:def __init__(self, value):self._left = None  # 左节点self._right = None  # 右节点self._data = value  # 该节点所指向的datadef insert_left_child(self, value):"""创建左子树:param value:"""if self._left:print("left child tree has already exists.")else:self._left = BinaryTree(value)return self._leftdef insert_right_child(self, value):"""创建右子树:param value:"""if self._right:print("right child tree has already exists.")else:self._right = BinaryTree(value)return self._rightdef show(self):print(self._data)def pre_order(self):"""前序遍历1.打印当前节点数据2.打印左子树节点数据，遍历左子树3.在叶子节点向根节点依次遍历右子树，打印节点数据"""print(self._data)if self._left:self._left.pre_order()if self._right:  # 注意：这里不要用elif,如果使用elif 会出现打印不全(叶节点没有子节点便不会进行后面的代码)self._right.pre_order()def post_order(self):"""后序遍历先右再左即可，先遍历打印右节点，再打印当前节点"""if self._right:self._right.post_order()if self._left:self._left.post_order()print(self._data)def in_order(self):if self._left:self._left.in_order()print(self._data)if self._right:self._right.in_order()if __name__ == '__main__':print("provided by chan zany")

provided by chan zany

栈

• 栈是一种后进先出(LIFO)或先进后出(FILO)的数据结构。

自定义栈结构

class Stack:def __init__(self, size=10):self._content = []  # 使用列表存放栈的元素self._size = size  # 初始栈大小self._current = 0  # 栈中元素个数初始化为0def empty(self):"""清空栈:return:"""self._content = []self._current = 0def is_empty(self):"""判断栈是否为空:return:"""if not self._content:return Trueelse:return Falsedef set_size(self, size):"""重置栈的大小:param size::return:"""# 如果缩小栈空间，则删除指定大小之后的已有元素if size < self._current:for i in range(size, self._current)[::-1]:del self._content[i]self._current = sizeself._size = sizedef is_full(self):if self._current == self._size:return Trueelse:return Falsedef push(self, v):if len(self._content) < self._size:self._content.append(v)self._current = self._current + 1  # 栈中元素+1，当前所指向的元素后移一位else:print('Stack Full!')def pop(self):if self._content:self._current = self._current - 1return self._content.pop()else:print('Stack is Empty!')def show(self):print(self._content)def show_remain_space(self):print('Stack can still PUSH', self._size - self._current, 'elements')if __name__ == '__main__':print('Please use me as a module----provided by ChanZany')

Please use me as a module----provided by ChanZany