vanCopper bio photo

vanCopper

Try Your Best.

Email Github

原创博文,转载请声明

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();
        }
    }
}

扫码分享该文