我们用易语言来写堆排序，难度非常大，堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

堆的操作

1、在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
2、最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
3、创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
4、堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

易语言堆排序

1、建堆

.版本 2
 
.子程序 建堆, , 公开, 以现有数据建堆（单维数组）
.参数 堆数据, 整数型, 参考 数组
.局部变量 index, 整数型
.局部变量 i, 整数型
 
重定义数组 (heap, 假, 取数组下标 (堆数据, ))
len ＝ 取数组下标 (heap, )
.变量循环首 (1, len, 1, i)
    heap [i] ＝ 堆数据 [i]
.变量循环尾 ()
.变量循环首 (len ÷ 2, 1, -1, i)
    调整 (i)
.变量循环尾 ()
返回 ()

2、堆调整adjust

.版本 2
.子程序 调整, , 公开, adjust(index,length)
.参数 起始节点, 整数型
.参数 终止节点, 整数型, 可空, 若为空则调整起始节点到最后一个元素
.局部变量 cur, 整数型
.局部变量 max, 整数型
.局部变量 lchild, 整数型
.局部变量 rchild, 整数型
 
.如果真 (len ＝ 0 或 起始节点 ＝ 0)
    返回 ()
.如果真结束
.如果真 (是否为空 (终止节点))
    终止节点 ＝ len
.如果真结束
lchild ＝ 2 × 起始节点
rchild ＝ 2 × 起始节点 ＋ 1
max ＝ 起始节点
.如果真 (起始节点 ≤ 终止节点 ÷ 2)
    .如果真 (lchild ≤ 终止节点 且 heap [lchild] ＞ heap [max])
        max ＝ lchild
    .如果真结束
    .如果真 (rchild ≤ 终止节点 且 heap [rchild] ＞ heap [max])
        max ＝ rchild
    .如果真结束
    .如果真 (max ≠ 起始节点)
        swap (heap [起始节点], heap [max])
        调整 (max)
    .如果真结束
.如果真结束
返回 ()

3、堆排序

4、swap

.版本 2
 
.子程序 swap
.参数 a, 整数型, 参考
.参数 b, 整数型, 参考
.局部变量 temp, 整数型
temp ＝ a
a ＝ b
b ＝ temp

5、堆的相关操作
.版本 2

.子程序 取堆节点数值, 整数型, 公开
.参数 下标, 整数型

.如果真 (len ＝ 0)
返回 (-1)
.如果真结束
返回 (heap [下标])

.子程序 交换堆节点, , 公开
.参数 下标1, 整数型
.参数 下标2, 整数型

.如果真 (len ＝ 0)
返回 ()
.如果真结束
swap (heap [下标1], heap [下标2])
调整 (1)

.子程序 取堆顶, 整数型, 公开, g
.局部变量 temp, 整数型

.如果真 (len ＝ 0)
返回 (-1)
.如果真结束
temp ＝ heap [1]
swap (heap [1], heap [len])
len ＝ len － 1
调整 (1)
返回 (temp)

.子程序 取堆大小, 整数型, 公开, get length

返回 (len)

.子程序 是否为空, 逻辑型, 公开

返回 (len ＝ 0)

.子程序 清空, , 公开

重定义数组 (heap, 假, 0)
len ＝ 0

.子程序 添加节点, , 公开
.参数 数值, 整数型
.局部变量 max, 整数型
.局部变量 i, 整数型

len ＝ len ＋ 1
重定义数组 (heap, 真, len)
heap [len] ＝ 数值
.变量循环首 (len ÷ 2, 1, -1, i)
调整 (i)
.变量循环尾 ()

.子程序 删除节点, , 公开
.参数 下标, 整数型
.局部变量 i, 整数型

heap [下标] ＝ heap [len]
len ＝ len － 1
.变量循环首 (len ÷ 2, 1, -1, i)
调整 (i)
.变量循环尾 ()