Question

堆排序怎么写

Answer 1

堆排序的写法是：根据拿到的数组构建大顶堆/小顶堆；从堆顶取走元素，放到其应该存在的位置中去。从堆底拿到堆中最后一个元素，放到堆顶，此时这个堆很可能不再合法也就是说不再是一个堆。

维护这个堆，通过自己写的方法调整堆中节点结构，让它重新变成一个堆；重复2，3过程，直到堆被取空，此时数组也被完全排列好。

可以发现堆排序并没有面向我们如何对于这个数组进行数值比较，如何排序，它的思路和其他的排序方式很不同，它是面向了一个堆的维护，而不是把重心放到了数组的排列上。

在堆排序中，最为耗费时间的时候就是堆的构建，一旦这个堆被构建好之后，从堆顶取元素，从堆底拿元素的行为就不会让这个堆变得特别无序，也就是说它肯定是比以前没有被构建的时候有序的多。

因此再维护起来，时间复杂度就会小很多，每次维护可能只会移动几个节点，因而效率就能够得到提升。接下来再进行堆排序的图解以及代码分析。

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

1、最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

2、创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。

3、堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。