本文共 3210 字,大约阅读时间需要 10 分钟。
什么是优先队列?
优先队列是一种数据结构,与普通的队列Queue是类似的,可以插入、删除、遍历队列中的元素。不同之处在于,在删除元素时,优先队列可以删除队列中最大/最小的元素。也就是说,在优先队列中,元素被赋予优先级。具有最高优先级的元素最先删除。
如何实现(Java)?
根据优先队列的特点,自然而然,我们想到优先队列的API应该有:初始化队列、插入元素、删除最高优先级元素(我们以删除最大值元素为例),锁定最高优先级元素——即进行比较等主要功能。
优先队列的关键在于:锁定优先级最高(最大值)的元素。如何做到呢?队列的实现可以用链表来实现,也可以用数组来实现。
上面两个方法,要么在插入操作上,要么在删除操作上,都需要遍历——时间复杂度为 O ( N ) O(N) O(N)。很明显过于复杂,是否有方法可以优化呢?
有,Binary Heaps(二叉堆)。
什么是二叉堆?
二叉堆形似二叉树,父元素总比子元素优先级高(在此例中是比子元素大),一个父结点有两个子节点,所以二叉堆的高度只有在 2 N 2^N 2N时增加。高度是 [ l g N ] [lgN] [lgN]。
Java如何实现?
由二叉堆的定义可知,队列的最大值总是在二叉堆的根部,所以删除元素时,只需要删除二叉堆的根部元素即可——可以将二叉堆的根部元素与最末尾的元素(最底层子元素)互换,删除交换后位于最末尾的最大元素,然后将暂时位于根部的子元素,根据二叉堆原则——根部元素总是要大于子元素,进行交换安置,完成删除操作;这一步有从上往下比对的操作sink(k)
:
插入元素时,首先将元素直接作为子节点插入二叉堆的末尾,然后不断比对子节点与父节点,直至子节点小于父节点,或者无父节点,如果子节点比父节点大,则进行交换,完成插入操作。这一步有从下往上比较的操作swim(k)
:
时间复杂度是多少?插入insert的时间复杂度为 l o g N logN logN,删除最大值delmax的时间复杂度为 l o g N logN logN。
比对用数组、链表实现的优先队列:
Heapsort是二叉堆的排序应用,称为堆排序。理解起来其实很简单,二叉堆的结构是最大的元素总是在根部,即我们每进行一次sink,总是能在根部获得数组最大值。那我们,先从二叉堆根部开始,进行exch与sink结合的操作,每次将最大值与最小子结点交换,然后sink最小子节点与剩下的元素,得到第二大的元素,不断循环操作,完成排序。
实现步骤:
- 使用冒泡法先将乱序的待排序列创建为二叉堆
- remove the maximum(移除根节点),然后对剩下的array进行sink
时间复杂度最差为 2 N l g N 2NlgN 2NlgN,最好为 N l g N NlgN NlgN,平均为 N l g N NlgN NlgN。
本次实验,涉及到A*算法。学习链接如下:
A *算法:是一种用于图形遍历和路径搜索的启发式搜索算法、最佳优先算法。
A *算法通过维护始于起始节点的路径树,并一次扩展一条路径,指导满足其终止条件。在每次循环中A *需要确定扩展的路径——最小化路径。根据成本函数: f ( n ) = g ( n ) + h ( n ) f(n) = g(n)+h(n) f(n)=g(n)+h(n)
其中, n n n是路径上的下一个节点; g ( n ) g(n) g(n)是从起始点到 n n n的路径成本; h ( n ) h(n) h(n)是启发式函数,用于估算 n n n到目标节点的最便宜成本。一般是曼哈顿距离。
A *的典型应用是使用优先队列,每次选择最小 f ( n ) f(n) f(n)(成本)的节点,此优先队列成为开放集。在算法的每个步骤中,从队列中删除具有最低成本的节点,并更新其相连节点的f和g的值后,将相邻节点添加到队列中,直到删除节点是目标节点后结束。
8-puzzle实现分析:
首先定义了一个Board对象,用来描述 N × N N×N N×N的一个数据结构。
可以将每种排列方式看成一个节点,而周边节点则是滑块移动后可能出现的排列方式。 将初始节点放入priority queue(优先队列)中 ,然后得到优先级最高的节点,并计算其相邻的节点,放入priority queue中,持续此过程,直到节点与目标节点相同为止。具体来说:将计算过程看作一个游戏决策树,每一个搜索节点都是游戏树上的一个节点,树的孩子对应节点的相邻搜索节点。每一步都会从队列中拿出优先级最高的节点,并将它相邻节点,放入游戏树和优先队列中。
什么是符号表?
符号表是一种存储键值对的数据结构,支持两种操作:将新的键值对插入符号表中;根据给定的键值查找对应的值。
无序符号表API:
有序符号表API:
操作时间复杂度:
顺序查找 vs 二分查找无序表
有序表
什么是二叉查找树?
二叉查找树BST全称为,Binary Search Trees,是一种数据结构,具有下列性质的二叉树:
private class Node{ private Key key; private Value val; private Node left, right; public Node(Key key, Value val) { this.key = key; this.val = val; }}
BST的API:
具体实现put
操作,如下:
public void put(Key key, Value val){ root = put(root, key, val);}private Node put(Node x, Key key, Value val){ if(x == null) return new Node(key, val); int cmp = key.compareTo(x.key); if( cmp < 0 ) x.left = put(x.left, key, val); else if( cmp > 0 ) x.right = put( x.rigth, key, val); else if ( cmp = 0 ) x.val = val; return x;}
时间复杂度:
转载地址:http://avzsi.baihongyu.com/