查询网站的外链,网站建设合作合同范文,设计网站官网国外,东莞网站建设营销网站我是一个计算机专业研0的学生卡蒙Camel#x1f42b;#x1f42b;#x1f42b;#xff08;刚保研#xff09;
记录每天学习过程#xff08;主要学习Java、python、人工智能#xff09;#xff0c;总结知识点#xff08;内容来自#xff1a;自我总结网上借鉴#xff0…我是一个计算机专业研0的学生卡蒙Camel刚保研
记录每天学习过程主要学习Java、python、人工智能总结知识点内容来自自我总结网上借鉴
希望大家能一起发现问题和补充也欢迎讨论目录 堆堆的介绍堆存储堆操作堆插入删除堆顶自底向上堆化自顶向下堆化 堆排序1. 建堆2. 排序 堆
堆的介绍
堆是一种特殊的树形数据结构通常以完全二叉树的形式表示并且满足堆属性。根据堆属性的不同堆可以分为两种类型
最大堆Max Heap对于每个节点它的值都大于或等于其子节点的值。因此堆顶元素根节点总是最大的。最小堆Min Heap对于每个节点它的值都小于或等于其子节点的值。因此堆顶元素根节点总是最小的。 堆存储 二叉堆可以用完全二叉树的形式进行存储。树中任意节点 i其左子节点序号为 2*i右子节点序号为 2*i1
堆操作
堆插入
将要插入的元素放到最后从底向上如果父结点比该元素小则该节点和父结点交换直到无法交换 删除堆顶
删除对顶元素是最大堆(最小堆)的最大值(最小值)为了保持堆的性质需要对堆的结构进行调整我们将这个过程称之为堆化有两种方法
自底向上的堆化自顶向下堆化
自底向上堆化
以大顶堆为例
先删除堆顶元素(即数组中index 1的位置)比较根结点的左子节点和右子节点(index 2和3)较大的元素放到根节点此时又有空位和步骤2一样空位两个子节点较大的移动到空位直到最底部 自顶向下堆化
我们将最后一个元素移动到堆顶。不停与左右子节点的值进行比较和较大的子节点交换位置直到无法交换位置。 堆排序
堆排序分为两个步骤
建堆排序
1. 建堆
建堆需要对所有非叶节点的自顶向下堆化。
顺序是从indexn/2到index1依次进行堆化
引用JavaGuide的图
一开始没排序前的数组n 6 所以要从索引为 3 到 1 的顺序进行堆化 对index3的节点进行堆化 对index2的节点进行堆化 对index1的节点进行堆化堆化完成 2. 排序
我们在第一步已经建堆完毕故堆顶元素就是最大值。所以我们重复取出堆顶元素将这个最大的堆顶元素放至数组末尾并对剩下的元素进行堆化即可。
取出堆顶元素并且堆化 一次取出堆顶并且优化
