# ヒープソート HeapSort
# 引数 値 (\@Price)
# 戻り値 ヒープソート (@HeapSort)
sub HEAPSORT{
	my ($Price) = @_;
	my @HeapSort = @$Price;
	my $Count = @$Price - 1;
	
	# 配列数の確認
	if($Count <= 0){
		return 0;
	}
	
	# 半順序木 ヒープ構造の作成
	for(my $i = 1; $i <= $Count; $i++){
		# 配列の位置
		my $ParentNum = int(($i - 1) / 2);
		my $ChildNum = $i;

		while($ChildNum != 0){
			if($HeapSort[$ChildNum] > $HeapSort[$ParentNum]){
				($HeapSort[$ChildNum], $HeapSort[$ParentNum]) = ($HeapSort[$ParentNum], $HeapSort[$ChildNum]);
			}

			$ChildNum = $ParentNum;
			$ParentNum = int(($ParentNum - 1) / 2);
		}
	}

	# 昇順ソート
	for(my $i = $Count; $i > 0; $i--){
		my $ParentNum = 0;
		my $Child = 1;
		# 根を後ろに持っていく
		($HeapSort[$ParentNum], $HeapSort[$i]) = ($HeapSort[$i], $HeapSort[$ParentNum]);

		while($Child < $i){
			# 子ノードBがソート済みではない と 子ノードA < 子ノードB
			$Child++ if(($Child < ($i - 1)) && ($HeapSort[$Child] < $HeapSort[$Child + 1]));
			# 親のノード < 子ノード
			if($HeapSort[$ParentNum] < $HeapSort[$Child]){
				($HeapSort[$ParentNum], $HeapSort[$Child]) = ($HeapSort[$Child], $HeapSort[$ParentNum]);
			}else {
				last;
			}

			# 配列の位置
			$ParentNum = $Child;
			$Child = (2 * $ParentNum) + 1;
		}
	}

	return @HeapSort;
}