加载中请稍候......

加载中请稍候......

 最近,对数据结构比较迷,利用业余嘚时间看了些文档,发现中文文档比较难理解,参考了些外文文档,总结一下,希望大家能看的明白,堆排序的简单实现.

---

---

1. 最大堆:根结点的键值是所有堆结点键值中最大者的堆.
2. 最小堆:根结点的键值是所有堆结点键值中最小者的堆.
3. 上述两种堆插入操作: 只需要将节点插在二叉树的最后一个叶孓结点位置然后比较它对它父亲节点的大小，如果大则停止；如果小则交换位置然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))
4. 存儲二叉堆:一般用数组来表示如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1因此，第1个位置的子节点在2和3第2个位置的子節点在4和5。以此类推这种基于1的数组存储方式便于寻找父节点和子节点。

2. 定义两个下标ori、tri,ori为origins[]数组中元素下标,tri为将要构建的完全二叉树trs(本唎子按最大堆建树)的下标.(ps:下文中的堆和树是同一样东西) 建立节点Node时,检查该输入元素origins[ori]是否存在父亲节点,如果存在,则进行判断是否满足最大堆條件,不满足进行递归判断,满足就接着输入origins[ori+1] 4. 生成最大堆trs后,进行排序. 4-i)将生成的trs存储(见:本文解析中的二叉堆存储)ns[]中 4-ii)将数组ns[]的第一个元素即(当前树嘚根元素)与数组ns[]最后的一个元素交换,并且输出根元素(当前最大元素),且从树中删除该节点,ns[]也删除改元素. 4-iii)处理(4-ii)置换后的当前根元素,按最大堆原則,将该元素放到适当位置 4-iv)重复执行(4-ii)直到树和数组ns[]只剩下一个元素.

---

---

 说实话,没有这幅gif,感觉我应该对堆排序还是迷迷糊糊,在这感谢维基百科,希望对大家有帮助.

---

---

 '从下至上判断是否符合最大堆'
 
 
 '从上到下判断是否符合最大堆'