/* 

  Sorting algorithms/Heapsort (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
  """
  Heapsort is an in-place sorting algorithm with worst case and average complexity of   
  O(n logn).

  The basic idea is to turn the array into a binary heap structure, which has the property 
  that it allows efficient retrieval and removal of the maximal element.

  We repeatedly "remove" the maximal element from the heap, thus building the sorted 
  list from back to front.

  A heap sort requires random access, so can only be used on an array-like data structure.

  ...

  Write a function to sort a collection of integers using heapsort.

  """

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.


main => go.

go =>
  _ = random2(),
  A = [random(-10,10) : _ in 1..30],
  println(A),
  heapSort(A),
  println(A),
  nl.

go2 =>
  _ = random2(),
  Good = ok,
  foreach(_ in 1..10_000, Good == ok)
    A = [random(1,10) : _ in 1..40],
    % A = [rand_cp(1,-100,100).first : _ in 1..3],
    println(a_before=A),
    heapSort(A),
    println('a_after '=A),
    if A == sort(A) then
      println(ok)
    else
      println(not_ok),
      Good := not_ok
    end,
    nl
  end,
  nl.


heapSort(A) =>
  heapify(A),
  End = A.len,
  while (End > 1)
    swap(A, End, 1),
    End := End - 1,
    siftDown(A, 1, End)
  end.

heapify(A) =>
  Count = A.len,
  Start = Count // 2,
  while (Start >= 1)  
    siftDown(A, Start, Count),
    Start := Start - 1
  end.
 
siftDown(A, Start, End) =>
  Root = Start,
  Loop = true,
  while (Root * 2 - 1 < End, Loop == true)
    Child := Root * 2- 1,
    if Child + 1 <= End, A[Child] @< A[Child+1] then
      Child := Child + 1
    end,
    if A[Root] @< A[Child] then
      swap(A,Root, Child),
      Root := Child
    else
       Loop := false
    end
  end.


% Swap position I <=> J in list L
% (inplace)
swap(L,I,J)  =>
  if I != J then
    T = L[I],
    L[I] := L[J],
    L[J] := T
  end.


rand_cp(N,Min,Max) = X =>
  _ = random2(),
  X = new_list(N),
  X :: Min..Max,
  solve($[rand_var,rand_val],X).