易语言堆排序

堆的操作

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

511遇见

511遇见

易语言堆排序

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、堆排序

  1. .版本 2
    
  2. .子程序 堆排序, , 公开
    
  3. .参数 待排序数组, 整数型, 参考 数组
    
  4. .局部变量 新数组, 整数型, , "0"
    
  5. .局部变量 i, 整数型
    
  6. .局部变量 k, 整数型
    
  7. .局部变量 toal, 整数型
    
  8. toal = 取数组成员数 (待排序数组)
    
  9. 建堆 (待排序数组)
    
  10. k = 取堆顶 ()
    
  11. i = 0
    
  12. .判断循环首 (k ≠ -1)
    
  13.     待排序数组 [i + 1] = k
    
  14.     i = i + 1
    
  15.     k = 取堆顶 ()
    
  16. .判断循环尾 ()

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)
.变量循环尾 ()


发布日期:

所属分类: 易语言 标签: