# -*- coding: utf-8 -*-
"""heap_sort.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/12lxwJdY5eO-QK4OOJ7WQh6mK0r87_AzB
"""

import numpy as np
import time

def max_heapify(arr, idx, n):
  while 2*idx+1 < n:
    L = 2*idx+1
    R = 2*idx+2

    if arr[idx] < arr[L]:
      m = L

    else:
      m = idx

    if R < n and arr[m] < arr[R]:
      m = R

    if idx != m:
      arr[idx], arr[m] = arr[m], arr[idx]
      idx = m

    else:
      break

def min_heapify(arr, idx, n):
  while 2*idx+1 < n:
    L = 2*idx+1
    R = 2*idx+2

    if arr[idx] > arr[L]:
      m = L

    else:
      m = idx

    if R < n and arr[m] > arr[R]:
      m = R

    if idx != m:
      arr[idx], arr[m] = arr[m], arr[idx]
      idx = m

    else:
      break

def make_heap(arr, isMaxHeap):
  if isMaxHeap == True:
    for i in range(len(arr)//2, -1, -1):
      max_heapify(arr, i, len(arr))

  else:
    for i in range(len(arr)//2, -1, -1):
      min_heapify(arr, i, len(arr))

def heap_sort(arr, isMaxHeap):
  make_heap(arr, isMaxHeap)
  n = len(arr)

  if isMaxHeap == True:
    for i in range(len(arr)-1):
      arr[0], arr[n-1] = arr[n-1], arr[0]
      n = n-1

      max_heapify(arr, 0, n)

  else:
    for i in range(len(arr)-1):
      arr[0], arr[n-1] = arr[n-1], arr[0]
      n = n-1

      min_heapify(arr, 0, n)

  return arr

def check_sort(arr, N, isMaxHeap):
  sorted = True

  if isMaxHeap==True:
    for i in range(N-1):
      if arr[i] > arr[i+1]:
        sorted = False
      if sorted == False:
        break;
    
    if sorted == True:
      print("Maxheap sorting complete!")
    else:
      print("Maxheap sorting error!!!")

  else:
    for i in range(N-1):
      if arr[i] < arr[i+1]:
        sorted = False
      if sorted == False:
        break;
    
    if sorted == True:
      print("Minheap sorting complete!")
    else:
      print("Minheap sorting error!!!")

print("MaxHeap 정렬 결과")
print(heap_sort([6, 2, 8, 1, 3, 9, 4, 5, 10, 7], isMaxHeap=True))
print("MinHeap 정렬 결과")
print(heap_sort([6, 2, 8, 1, 3, 9, 4, 5, 10, 7], isMaxHeap=False))

N_list = [10000, 50000, 100000, 500000, 1000000]

for N in N_list:
  arr = np.random.randint(low=0, high=N, size=N) # 길이가 N개인 임의의 리스트를 생성

  isMaxHeap=True
  start = time.time()  
  sorted_arr = heap_sort(arr.copy(), isMaxHeap)
  cost = round(time.time() - start, 2)
  check_sort(sorted_arr, N, isMaxHeap)
  print(f"Maxheap sorting (N={N}) time cost : {cost}sec")

  isMaxHeap=False
  start = time.time()  
  sorted_arr = heap_sort(arr.copy(), isMaxHeap)
  cost = round(time.time() - start, 2)
  check_sort(sorted_arr, N, isMaxHeap)
  print(f"Minheap sorting (N={N}) time cost : {cost}sec\n")

