ラボ/ヒープ

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74

 
 
 
 
 
-
-
|
!
!
-
|
|
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-
|
|
|
!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

#module HeapSample
// startIndex以下の子要素のバランスを取る
#deffunc hsArgo array target, int startIndex, int endIndex, local child, local tmp
    child = (startIndex + 1) * 2 - 1
    if child > endIndex : return
    if child + 1 <= endIndex {
        if target(child) < target(child + 1) {
            child++
        }
    }
    if target(startIndex) < target(child) {
        tmp = target(child)
        target(child) = target(startIndex)
        target(startIndex) = tmp
        hsArgo target, child, endIndex
    }
    return
 
// ヒープの作成(ルートが最大値になる)
#deffunc hsMakeHeap array target, local tmp, local i
    for i, length(target) / 2 - 1 , -1, -1
        hsArgo target, i, length(target) - 1
    next
    return
 
// 2のi1乗
#defcfunc pow2 int i1
    return 1 << i1
 
// ヒープの描画（乱雑）
#deffunc heapMes array target, local i, local l, local y
    i = 0 : repeat
        i += pow2(cnt)
        if length(target) <= i : i = cnt+1 : break
    loop
 
    l = 0 : y = ginfo_cy
    repeat i
        up_cnt = cnt
        repeat pow2(cnt)
            pos ginfo_winx * (cnt + 1) / (pow2(up_cnt) + 1), y
            mes target(l)
            if up_cnt {
                color 0, 128, 128
                line ginfo_winx * (cnt + 1) / (pow2(up_cnt) + 1)+8, y+8, ginfo_winx * (cnt/2 + 1) / (pow2(up_cnt - 1) + 1)+8,  y-30+8
                color
            }
            l++
            if l>=length(target) : break
        loop
        y += 30
        if l>=length(target) : break
    loop
    pos 0, y
    return
#global
 
// 以下 動作確認用サンプル
    randomize
    dim test, 15
    repeat length(test)
        test(cnt) = rnd(100)
    loop
 
    pos 0, 0
    mes "ソート前"
    heapMes test
 
    hsMakeHeap test
    pos 0, ginfo_winy/2
    mes "ヒープ作成後"
    heapMes test
 
    stop