ActionScript入門Wiki

var data:Array = [4, 1, 6, 2, 9, 7, 3, 8];
 

var left:int = parent * 2 + 1;	// 左の子
var right:int = left + 1;	// 右の子
 

private function heapSort(data:Array):void
{
	ヒープを構築(子を持っているノード全て);
 
	ループ
	{
		先頭ノードと末尾ノードを交換
		ヒープを構築(先頭ノード);
	}
}
 

/**
 * 
 * @param	data ソート対象配列
 * @param	parent このparentインデックスのノードを適切な位置に移動させる
 * @param	length 未確定ノード数
 */
private function makeHeap(data:Array, parent:int, length:int):void
{
	while (true)
	{
		// 左の子インデックスを取得
		var child:int = parent * 2 + 1;
 
		// 左の子インデックスがlength以上ということは子が無いので構築終了
		if (child >= length) return;
 
		//　左の子 + 1がlength未満なら右の子が存在する
		// 左の子より右の子要素値が小さい場合 = 親と交換するのは左の子
		// 左の子より右の子要素値が大きい場合 = 親と交換するのは右の子
		if (child + 1 < length && data[child] < data[child + 1]) child++;
 
		// 子のほうが値が大きい
		if (data[parent] < data[child])
		{
			// 親と子を交換
			var temp:int = data[parent];
			data[parent] = data[child];
			data[child] = temp;
 
			// 交換したので、対象ノードのインデックスがchildに変わる
			parent = child;
		}
		// 親のほうが値が大きいので交換する必要が無い。構築終了
		else break;
 
		// 親 > 子になるまでループ
	}
}
 

private function heapSort(data:Array):void
{
	// 下側のノード(配列の右側)から順番にヒープを構築
	for (var y:int = (data.length - 2) / 2; y >= 0; y--)
	{
		makeHeap(data, y, data.length);
	}
 
	// lastは未確定ノード群の末尾インデックス
	for (var last:int = data.length - 1; last >= 1; last--)
	{
		// 先頭ノードと末尾ノードを交換
		var temp:int = data[0];
		data[0] = data[last];
		data[last] = temp;
 
		// 交換したことによってヒープ構造が崩れた可能性がある
		// なので先頭(0番目)ノードを構築し直す
		makeHeap(data, 0, last);
	}
}
 

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var data:Array = [4, 1, 6, 2, 9, 7, 3, 8];
			heapSort(data);
			trace(data);
		}
 
		private function heapSort(data:Array):void
		{
			for (var y:int = (data.length - 2) / 2; y >= 0; y--)
			{
				makeHeap(data, y, data.length);
			}
 
			for (var last:int = data.length - 1; last >= 1; last--)
			{
				var temp:int = data[0];
				data[0] = data[last];
				data[last] = temp;
 
				makeHeap(data, 0, last);
			}
		}
 
		private function makeHeap(data:Array, parent:int, length:int):void
		{
			while (true)
			{
				var child:int = parent * 2 + 1;
				if (child >= length) return;
				if (child + 1 < length && data[child] < data[child + 1]) child++;
				if (data[parent] < data[child])
				{
					var temp:int = data[parent];
					data[parent] = data[child];
					data[child] = temp;
 
					parent = child;
				}
				else break;
			}
		}
	}
}