斯坦福算法专项课程Course2 week3算法实现

这次回顾Course2 week3的算法。

课程地址：https://www.coursera.org/specializations/algorithms

Heap

class Heap():
    def __init__(self, Type):
        '''
        type定义堆类型，x=1表示最小堆, x=0表示最大堆
        '''
        #堆的索引从1开始，堆守存放一个无用的元素
        self.heap = [-1]
        self.len = 0
        #type定义堆类型，x=1表示最小堆, x=0表示最大堆
        self.type = Type
    
    def insert(self, x):
        '''
        插入
        '''
        #进入数组
        self.heap.append(x)
        #更新长度
        self.len += 1
        #索引
        i = self.len
        #最小堆
        if self.type == 1:
            while (i >= 2):
                #不满足最小堆的定义时交换父子
                if self.heap[i] < self.heap[i // 2]:
                    self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
                    i = i // 2
                else:
                    break
        #最大堆
        elif self.type == 0:
            while (i >= 2):
                #不满足最大堆的定义时交换父子
                if self.heap[i] > self.heap[i // 2]:
                    self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
                    i = i // 2
                else:
                    break
    
    def peek(self):
        #返回最小值（最大值），不删除
        return self.heap[1]

    def extract(self):
        '''
        弹出最小值（最大值）
        '''
        #交换元素
        self.heap[1], self.heap[-1] = self.heap[-1], self.heap[1]
        #目标元素
        a = self.heap[-1]
        #删除元素
        del self.heap[-1]
        #索引
        i = 1
        #更新长度
        self.len -= 1
        n = self.len
        #最小堆
        if self.type == 1:
            while (i <= n / 2):
                #左节点的位置
                j = 2 * i
                #找到更小的子节点
                if (j + 1 <= n and self.heap[j + 1] < self.heap[j]):
                    j += 1
                #不满足最小堆的定义时交换父子
                if self.heap[i] > self.heap[j]:
                    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
                    i = j
                else:
                    break
        #最大堆
        elif self.type == 0:
            while (i <= n / 2):
                    #左节点的位置
                    j = 2 * i
                    #找到更小的子节点
                    if (j + 1 <= n and self.heap[j + 1] > self.heap[j]):
                        j += 1
                    #不满足最大堆的定义时交换父子
                    if self.heap[i] < self.heap[j]:
                        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
                        i = j
                    else:
                        break
        return a

Binary Search Tree

import numpy as np

class BST():
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
    
    def search(self, data):
        if (self.data == data):
            return data
        elif (data < self.data):
            if (self.lchild != None):
                return self.lchild.search(data)
            else:
                return None
        else:
            if (self.rchild != None):
                return self.rchild.search(data)
            else:
                return None
        
    def insert(self, data):
        if (data < self.data):
            if (self.lchild != None):
                self.lchild.insert(data)
            else:
                self.lchild = BST(data)
        else:
            if (self.rchild != None):
                self.rchild.insert(data)
            else:
                self.rchild = BST(data)
                
    def in_order(self):
        if (self.lchild != None):
            self.lchild.in_order()
        print(self.data)
        if (self.rchild != None):
            self.rchild.in_order()

####测试
lst = np.random.randint(0, 100, 30)
Bst = BST(0)
for i in lst:
    Bst.insert(i)
Bst.in_order()

lst = np.random.randint(0, 100, 5)
for i in lst:
    print(i, Bst.search(i))