heap.nim

import system,random
discard """ヒープソート
最大ヒープ、親より大きな子孫は存在しない
"""

proc build(arr:var seq[int]):void
proc debuild(arr:var seq[int]):void
proc getLeftChild(index:int):int
proc getRightChild(index:int):int
proc getParent(index:int):int

var
  testdata:seq[int]
testdata= newseq[int](0)
for i in 0..1000:
  testdata.add(i)
randomize()
for i in 0..1000:
  swap(testdata[i],testdata[i+rand(max=1000-i)])

build(testdata)
echo testdata
debuild(testdata)
echo testdata

proc build(arr:var seq[int]):void=
  for i,j in arr:
    var a=i
    while arr[getParent(a)]<j:
      swap(arr[getParent(a)],arr[a])
      a=getParent(a)

proc debuild(arr:var seq[int]):void=
  let l:int=arr.len
  for i,j in arr:
    if i==l-1:
      break
    swap(arr[0],arr[l-i-1])
#    echo "before:", arr
    var
      a=0
      c:int
    while true:
      c=getRightChild(a)
      if(c>=l-i-1):
        break
      if arr[c]<arr[c-1]:
        c-=1
#      echo "compare arr[a]<=>arr[c]:"& $arr[a]& "," & $arr[c]
      if arr[a]<arr[c]:
        swap(arr[a],arr[c])
        a=c
      else:
        break
#    echo "after:", arr


proc getParent(index:int):int=
  result=index
  if result!=0:
    result=(result-1) div 2

proc getRightChild(index:int):int=
  return (index+1)*2

proc getLeftChild(index:int):int=
  return getRightChild(index)-1