package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序數(shù)組序列
   * @return 排好序的數(shù)組序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 調(diào)整堆
   *
   * @param nums  待排序序列
   * @param parent   待調(diào)整根節(jié)點(diǎn)
   * @param length 數(shù)組序列長(zhǎng)度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉樹節(jié)點(diǎn)i從編號(hào)1開始的左子節(jié)點(diǎn)位置在2i，此處數(shù)組下標(biāo)從0開始，即左子節(jié)點(diǎn)所在數(shù)組索引位置為：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //節(jié)點(diǎn)有右子節(jié)點(diǎn)，且右子節(jié)點(diǎn)大于左子節(jié)點(diǎn)，則選取右子節(jié)點(diǎn)
      }
      if (temp > nums[childIndex]) {
        break; //如果選中節(jié)點(diǎn)大于其子節(jié)點(diǎn)，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //繼續(xù)向下調(diào)整
    }
    nums[parent] = temp;
  }
}

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#調(diào)整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)