In this example you will see: Heapsort algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

example_4.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

class HeapSort{

	private var data : Array<Int>;
	private var heap_size : Int;
	private inline function leftChild(index : Int) : Int{ return (index << 1) + 1;	}
	private inline function rightChild(index : Int) : Int{ return (index << 1) + 2; }

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>){
		this.data = (data == null) ? new Array() : data;
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		this.data = data;
	}

	public function sort() : Void{
		if(data.iterator().hasNext()){
			heap_size = data.length;
			buildMaxHeap();
			var index : Int = data.length - 1;
			while (index > -1){
				exchange(0, index);
				maxHeapify(0, --heap_size);
				--index;
			}
		}else{
			trace('There is no data to sort');
		}
	}

	private function buildMaxHeap() : Void{
		var index : Int = data.length >> 1;
		while (index > -1){
			maxHeapify(index, heap_size);
			--index;
		}
	}

	private function maxHeapify(index : Int, heapSize : Int) : Void{
		var largest : Int = index;
		var left : Int = leftChild(index);
		var right : Int = rightChild(index);	

		if (left < heapSize && data[left] > data[index])
			largest = left;

		if (right < heapSize && data[right] > data[largest])
			largest = right;

		if (largest != index){
			exchange(index, largest);
			maxHeapify(largest, heapSize);
		}
	}

	private function exchange(index_a : Int, index_b : Int) : Void{
		var temp_value : Int = data[index_a];
		data[index_a] = data[index_b];
		data[index_b] = temp_value;
	}

}

class Example_4 {

	static function main(){

		var data : Array<Int> = [3, 7, 5, -1, 6, 1];
		printData(data);

		trace('heapsort:');
		var heapsort = new HeapSort(data);
		trace('sorting...');
		heapsort.sort();
		data = heapsort.getData();
		printData(data);		

		data = [3, 7, 5, -1, 6, 1];
		printData(data);		

		trace('heapsort_2:');
		var heapsort_2 = new HeapSort();
		trace('sorting without data...');
		heapsort_2.sort();
		trace('sorting with data...');
		heapsort_2.setData(data);
 		heapsort_2.sort();
 		printData(data);

	}

	private static function printData(data : Array<Int>){
		var iter = data.iterator();
		var index : Int = 0;
		trace('[DATA]');
		while (iter.hasNext()){
			trace('data[' + index++ + ']: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

*

Click to Insert Smiley

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeletonBunnyCatCat 2ChickChickenChicken 2CowCow 2DogDog 2DuckGoatHippoKoalaLionMonkeyMonkey 2MousePandaPigPig 2SheepSheep 2ReindeerSnailTigerTurtleBeerDrinkLiquorCoffeeCakePizzaWatermelonBowlPlateCanFemaleMaleHeartBroken HeartRoseDead RosePeaceYin YangUS FlagMoonStarSunCloudyRainThunderUmbrellaRainbowMusic NoteAirplaneCarIslandAnnouncebrbMailCellPhoneCameraFilmTVClockLampSearchCoinsComputerConsolePresentSoccerCloverPumpkinBombHammerKnifeHandcuffsPillPoopCigarette