JavaScript复制
发表于
|
分类于
JavaScript
优先队列的堆实现
发表于
|
分类于
Python
优先队列的堆实现
堆及其性质
- 采用树形结构实现优先队列的一种有效技术成为 堆,节点数据的存储满足堆序。
- 从根到任何一个叶节点,节点数据优先级递减
- 堆顶元素优先级最高,O(1)时间即可得到
- 位于不同路径上的元素,这里不关心其顺序
- 几个重要性质
- 在一个堆最后追加一个元素,依然是完全二叉树,但未必是堆
- 去掉堆顶,两个子堆上堆序不变
- 去掉堆顶的两个子堆加入根元素,未必是堆(堆序无法保证)
- 去掉堆中最后的元素,不破坏堆序
优先队列的连续列表实现
发表于
|
分类于
Python
优先队列的连续列表实现
两种实现方案
- 存储数据时保证元素的优先顺序,任何时候取元素都可以得到最高优先级(存入操作效率低,访问和弹出方便)
- 存入简单(顺序表存入表尾,链接表存入表头),取用时检索(存入效率高,访问弹出不便),如许多次访问统一元素但不弹出,则不采用此法,避免重复检索,或者记录要访问的元素位置。
其他
发表于
|
分类于
其他
了解点概念
DNS流量分发
容器调度:HP Ku8 Mannager
功能测试,性能测试
资源需求,项目时间节点
WEB应用层,能力服务器,数据库,高可用
背包问题
发表于
|
分类于
Python
栈的应用其二:背包问题
处理逻辑
knap(weight,n)
表示n件物品的重量- 若不选最后一件物品(重量为W(n-1)),
knap(weight,n-1)
的解即为knap(weight,n)
的解 - 若选择最后一件物品,若
knap(weight-W(n-1),n-1)
有解,其解加上最后一件物品就是kanp(weight,n)
的解,即前者有解后者也有解
- 若不选最后一件物品(重量为W(n-1)),
递归的考虑问题,n件物品的背包问题可归结为两个n-1件物品的背包问题:
- 同样重量,物品数量减一
- 减少重量,物品数量减一
简单的括号匹配
发表于
|
分类于
Python