堆、栈、队列及其Python的简单实现

栈

LIFO: last-in, first-out 后进先出 可以用一个数组S[1..n]来实现一个最多可容纳n个元素的栈。该数组有一个属性S.top， 指向最新插入的元素。栈中包含的元素为S[1..S.top]，其中S[1]是栈底元素，S[S.top]是栈顶元素。

两种操作： 1. PUSH：压入，栈上的INSERT操作，时间复杂度O(1) 2. POP：弹出，栈上的DELETE操作，时间复杂度O(1)

两种错误： 1. 栈下溢(underflow)：试图对一个空栈执行弹出操作 2. 栈上溢(overflow)：试图对一个已满的栈执行压入操作

python实现

class UNDERFLOW(Exception):pass # 下溢
class OVERFLOW(Exception):pass # 上溢
class Stack(object):
    def __init__(self, size):
        self.top = -1 #指向最新插入的元素
        self.S = [0 for _ in range(0,size)]
        self.size = size
    #测试一个栈是否为空
    STACK_EMPTY = lambda self: self.top == -1
    #测试一个栈是否已满
    STACK_FULL = lambda self: self.top == self.size-1
    #插入元素到栈顶
    def PUSH(self,x):
        if self.STACK_FULL():
 
               raise OVERFLOW("stack is full")
        self.top += 1
        self.S[self.top] = x
    #将栈顶元素返回并删除
    def POP(self):
        if self.STACK_EMPTY():
            raise UNDERFLOW("stack is empty")
        x = self.S[self.top]
        self.top -= 1
        return x

说明： 可以直接用python中的list来实现栈。PUSH操作相当于list.append(x)，POP操作相当于list.pop()

队列

FIFO: first-in, first-out 先进先出

队列有队头和队尾，当一个元素入队时，被放在队尾的位置；而出队的元素则总是在队头的那个。 利用数组Q[1..n]来实现含有n-1个元素队列（保留一位元素用来判断队列空或满）。该队列有一个属性Q.head指向对头元素，属性Q.tail指向下一个新元素将要插入的位置，队列中的元素存放在位置Q.head, Q.head+1, ..., Q.tail-1上。 初始时，Q.head = Q.tail = 1。当Q.head = Q.tail时， 队列为空。当Q.head=Q.tail+1时，队列是满的。

两种操作： 1. ENQUEUE：入队，队列上的INSERT操作，时间复杂度O(1) 2. DEQUEUE：出队，队列上的DELETE操作，时间复杂度O(1)

python实现

class UNDERFLOW(Exception):pass # 下溢
class OVERFLOW(Exception):pass # 上溢
class Queue(object):
    def __init__(self,size):
        self.head = self.tail = 0
        self.S = [0 for _ in range(0,size)]
        self.size = size
    # 判断队列是否已满
    QUEUE_FULL = lambda self: self.head == (self.tail+1)%self.size
    # 判断队列是否为空
    QUEUE_EMPTY = lambda self: self.head == self.tail
    # 入队
    def ENQUEUE(self, x):
        if self.QUEUE_FULL(): raise OVERFLOW("the queue is full")
        self.S[self.tail] = x
        self.tail = (self.tail+1) % self.size
    # 出队
    def DEQUEUE(self):
        if self.QUEUE_EMPTY(): raise UNDERFLOW("the queue is empty")
        x = self.S[self.head]
        self.head = (self.head+1) % self.size
        return x

注： 可以使用python中的collections.deque来实现队列。ENQUEUE相当于deque.append(), DEQUEUE相当于deque.popleft()

堆

在九大排序算法及其Python实现之堆排序中已经基本讲述了堆的性质。 下面讲讲堆的应用之一：优先队列 优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字(key)。 一个最大优先队列S支持以下操作： 1. INSERT(S, x)：把元素x插入集合S中。 2. MAXIMUM(S)：返回S中具有最大键值的元素 3. EXTRACT-MAX(S)：去掉并返回S中的具有最大键值的元素 4. INCREASE-KEY(S, x, k)：将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值。

实现

伪代码：

# 时间复杂度：O(1)
HEAP-MAXIMUM(S)
    return S[1]
# 时间复杂度：O(logn)
HEAP-EXTRACT-MAX(S)
    if S.heap-size < 1
        error "heap underflow"
    max = S[1]
    S[1] = S[S.heap-size]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)
    return max
# i为x的下标
# 时间复杂度：O(logn)
HEAP-INCREASE-KEY(S, i, k)
    if k < S[i]
        error "new key is smaller than current key"
    A[i] = key
    while i > 1 and A[PARENT(i)] < A[i] # 维护优先队列，即维护最大堆
        exchange A[i] with A[PARENT(i)]
        i = PARENT(i)
# key表示元素x的值
# 时间复杂度：O(logn)
MAX-HEAP-INSERT(S, key)
    A.heap-size = A.heap-size + 1
    A[heap-size] = -∞
    HEAP-INCREASE-KEY(S, A.heap-size, key)

## python实现

class UNDERFLOW(Exception):pass # 下溢
class OVERFLOW(Exception):pass # 上溢
class BADVALUE(Exception): pass #错误的值
# 最大堆
class Heap(object):
    def __init__(self, A):
        self.S = A[:]
        self.size = self.heap_size = len(A)
        self._BUILD_MAX_HEAP()
    
    PARENT = lambda self, i: i/2 #获得i的父结点下标
    LEFT = lambda self, i: 2*i # 获得i的左子树的根结点下标
    RIGHT = lambda self, i: 2*i+1 # 获得i的右子树的根结点下标
        
    def MAX_HEAPIFY(self, i): # 维护最大堆
        left, right = self.LEFT(i), self.RIGHT(i)
        largest = left if left < self.heap_size and self.S[left] > self.S[i] else i
        largest = right if right < self.heap_size and self.S[right] > self.S[largest] else largest
        if largest != i:
            self.S[i], self.S[largest] = self.S[largest], self.S[i]
            self.MAX_HEAPIFY(largest)
    
    def _BUILD_MAX_HEAP(self): # 构建最大堆
        for i in range(self.PARENT(self.size-1),-1,-1):
            self.MAX_HEAPIFY(i)
    # 最大优先队列
    def INSERT(self, key): # 插入key到堆中
        if self.heap_size >= self.size: raise OVERFLOW("the heap is full")
        self.heap_size += 1
        self.S[self.heap_size-1] = float('-INF')
        self.INCREASE_KEY(self.heap_size-1, key)
    def MAXIMUM(self): # 获得堆中最大元素
        return self.S[0]
    def EXTRACT_MAX(self): # 删除并返回堆中最大元素
        if self.heap_size < 1: raise UNDERFLOW("the heap is empty")
        max = self.S[0]
        self.S[0] = self.S[self.heap_size-1]
        self.heap_size -= 1
        self.MAX_HEAPIFY(0)
        return max
    def INCREASE_KEY(self, i, key): # 将下标为i的值增加到key值，维护最大堆
        if self.S[i] > key: raise BADVALUE("new key is smaller than current key")
        self.S[i] = key
        while i> 0 and self.S[i] > self.S[self.PARENT(i)]:
            self.S[i], self.S[self.PARENT(i)] = self.S[self.PARENT(i)], self.S[i]
            i = self.PARENT(i)