首页 > 编程知识 正文

小根堆排序解,小根堆大根堆应用题

时间:2023-05-04 15:37:04 阅读:267758 作者:4651

小根堆


如果有一个关键字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉树的顺序存储
方式存放在一个一维数组中,并且满足
ki <= k2i+1 且 ki <= k2i+2  (i = 0, 1, ..., (n-2)/2 向上取整)
则称这个集合为小根堆。

小根堆的创建:
1. 复制堆数组
2. 找到最初的调整位置,即最后一个分支结点
3.1自底向上逐步扩大形成堆
3.2 向前换一个分支结点

小根堆的插入:
1. 将待插入元素插入已建成堆的最后面
2. 沿着出入位置所在的分支逐步向上调整

小根堆的删除:
1. 将顶元素删除

2. 将数组中最后一个元素放到堆顶

3. 自顶向下调整







版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。