堆(Heap)AS3版

深碍√TFBOYSˉ_ 2022-08-25 12:51 93阅读 0赞

当应用优先级队列或者进行堆排序时，一般利用堆来实现。堆是一个完全二叉树，并满足如下条件：  
1、根结点若有子树，则子树一定也是堆。  
2、根结点一定大于（或小于）子结点。  
因为要求堆必须是完全二叉树，所以使用数组实现堆要比结点实现更有效率。  
利用数组实现，则对于长为N的堆中的元素从0到N-1排列，有：  
1、i 的父结点：Parent(i)=(i+1)/2-1  
2、i 的左叶子：Left(i)=(i+1)\*2-1  
3、i 的右叶子：Right(i)=(i+1)\*2  
堆的插入和删除很有意思。在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义了以下几种操作，在堆中进行了上述操作后，堆的特殊属性可能发生变化。例如，当在堆尾插入一个数据，它可能大于它的父节点，因而需要进行一系列的置换操作，调整它的位置，从而保持堆的特有属性。和此相关的操作包括：  
筛选上移（sift\_up）：给定某个数据后，将其上移到相应的位置，从而保证其值不大于父节点。  
筛选下移（sift\_down）：给定某个数据后，将其下移到相应的位置，从而保证其值不大于父节点。  
堆主要应用在排序算法中。  
  
  
package kono.utils  
\{  
//堆，基于数组， Heap, built on a array  
public class Heap  
\{  
private var \_heap:Array;  
private var \_top:uint;  
private var capacity:uint;  
private var compare:Function;  
  
public function Heap(size:uint, compareTo:Function = null)  
\{  
\_heap = new Array(capacity = size);  
\_top = 0;  
if(compareTo == null)  
\{  
compare = function (a:Number, b:Number):int  
\{  
return int(a-b);  
\}  
\}  
else  
\{  
compare = compareTo;  
\}  
\}  
  
//得到堆的大小， get the heap????s capacity  
public function get size():uint  
\{  
return capacity;  
\}  
  
//堆首， the first data in the heap  
public function peek():\*  
\{  
return \_heap\[0\];  
\}  
  
//添加新数据到堆（sift\_up）， add a new data to heap  
public function push(data:\*):void  
\{  
\_heap\[\_top\] = data;  
var parents:uint = (\_top - 1) >> 1;  
while(\_top > 0 && parents >= 0)  
\{  
if(compare(\_heap\[\_top\], \_heap\[parents\]) > 0)  
\{  
var temp:\* = \_heap\[parents\];  
\_heap\[parents\] = \_heap\[\_top\];  
\_heap\[\_top\] = temp;  
if(parents > 0)  
parents = (parents - 1) >> 1;  
\}  
else  
break;  
\}  
\_top ++;  
\}  
  
//删除堆首元素（sift\_down）， remove the first data in the heap  
public function pop():void  
\{  
if(\_top > 0)  
\{  
\_heap\[0\] = \_heap\[\_top -1\];  
var cursor:uint = 0;  
var childs:uint = (\_top << 1) + 1;  
childs = \_heap\[childs\] > \_heap\[childs + 1\] ? childs : childs + 1;  
while(childs < \_top)  
\{  
if(compare(\_heap\[cursor\], \_heap\[childs\]) < 0)  
\{  
var temp:\* = \_heap\[cursor\];  
\_heap\[cursor\] = \_heap\[childs\];  
\_heap\[childs\] = temp;  
cursor = childs;  
\}  
else  
break;  
\}  
\_top--;  
\}  
delete \_heap\[\_top\];  
\}  
  
//打印堆结构， print the frame of the heap  
public function print():void  
\{  
var space:String = " ";  
for(var i:uint = 0; i < \_heap.length; i++)  
\{  
space += " ";  
trace(space + \_heap\[i\]);  
\}  
\}  
  
//清空堆， remove all the data of the heap  
public function clear():void  
\{  
\_heap = new Array(capacity);  
\_top = 0;  
\}  
  
//判断给定数据是否包含在堆中， check if the given target exit in the heap  
public function contains(target:\*):Boolean  
\{  
for(var i:uint = 0; i < \_heap.length; i++)  
\{  
if(\_heap\[i\] == target)  
\{  
return true;  
\}  
\}  
return false;  
\}  
  
//转换堆到数组， convert the heap to a array  
public function toArray():Array  
\{  
return \_heap;  
\}  
  
//返回堆的信息， return a string respreaenting the current heap  
public function toString():String  
\{  
return "\[Heap, size=" + capacity + "\]";  
\}  
\}  
\}  
  
本文转自  
[http://www.moorwind.com/read.php?42][http_www.moorwind.com_read.php_42]

[http_www.moorwind.com_read.php_42]: http://www.moorwind.com/read.php?42