用于A*的二叉堆 AS3实现-白红宇

用于A*的二叉堆 AS3实现

阅读量：6531 次

发布时间：2019-06-24

本文共 1753 字，大约阅读时间需要 5 分钟。

package

com.copper.isometric.pathing

import

flash.sampler.startSampling;

/**

* A*中用于开放列表的二叉堆

* @author vanCopper

*

*/

public

class

BinaryHeap

private

var

struct:

Array

= [-

1

];

private

var

compareFunc:Function =

function

(x:

Object

,y:

Object

):

Boolean

if

(y ==

null

)

return

true

;

return

x < y;

};

/**

*

* @param compareFunc n

*

* function (x:Object,y:Object):Boolean

* {

* return x < y;

* };

*/

public

function

BinaryHeap(compareFunc:Function =

null

)

if

(compareFunc !=

null

)

this

.compareFunc = compareFunc;

}

/**

* 向二叉堆添加新元素

* @param value

*

*/

public

function

insert(value:

Object

):

void

if

(value ==

null

)

return

;

var

len:

int

= struct.length;

struct[len] = value;

var

parent:

int

= len >>

1

;

while

(parent >=

1

&& compareFunc(struct[len],struct[parent]))

var

temp:

Object

= struct[parent];

struct[len] = temp;

struct[parent] = value;

len = parent;

parent = parent >>

1

;

}

/**

* 删除二叉堆的第一个元素并返回该元素

* @return

*

*/

public

function

shift():

Object

var

n:

int

=

1

;

var

shiftObj:

Object

= struct[n];

if

(shiftObj ==

null

)

return

null

;

var

len:

int

= struct.length;

struct[n] = struct[len -

1

];

struct.length --;

var

moveObj:

Object

= struct[n];

var

left:

int

= n <<

1

;

var

right:

int

= left +

1

;

var

endLen:

int

= struct.length;

while

(right < endLen)

var

min:

int

= compareFunc(struct[left],struct[right]) ? left : right;

if

(compareFunc(moveObj,struct[min]))

// 停止二叉堆完成

break

;

}

else

var

tempObj:

Object

= struct[min];

struct[min] = moveObj;

struct[n] = tempObj;

n = min;

left = n <<

1

;

right = left +

1

;

}

return

shiftObj;

}

public

function

get

length():

int

return

struct.length;

}

public

function

toString():

String

return

struct.toString();

}

转载于:https://www.cnblogs.com/ch06src/p/3430940.html

你可能感兴趣的文章