java理解优先级队列中的排序方法
我有一个我同学写的代码
问题是我无法理解排序方法的功能
据我所知,它命令优先级队列没有被修改。 相反,heapify方法是一种有助于操纵堆(在本例中是一个最小堆)的方法,它允许元素a[i]向下滚动堆,直到它到达正确的位置
我错了吗
package priorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.NoSuchElementException;
public class BinaryHeap
{
protected static <P,E> Element<P,E> extractMinimum(ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping) throws NoSuchElementException
{
if (priorityQueue.size() == 0)
throw new NoSuchElementException();
if (priorityQueue.size() == 1)
return priorityQueue.remove(0);
Element<P,E> first = priorityQueue.get(0);
mapping.remove(first.getElement());
Element<P,E> newFirst = priorityQueue.get(priorityQueue.size()-1);
mapping.remove(newFirst.getElement());
priorityQueue.set(0, priorityQueue.remove(priorityQueue.size()-1));
mapping.put(newFirst.getElement() , 0);
heapify(priorityQueue, priorityComparator, mapping,0);
return first;
}
protected static <P,E> void sort (ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping, int index)
{
int i = index;
while(i > 0)
{
int middle = (i - 1)/2;
Element<P,E> element = priorityQueue.get(i);
Element<P,E> parent = priorityQueue.get(middle);
if(priorityComparator.compare(element, parent)<0)
{
mapping.replace(element.getElement(), middle);
mapping.replace(parent.getElement(), i);
priorityQueue.set(i, parent);
priorityQueue.set(middle, element);
i = middle;
}
else
break;
}
}
protected static <P,E> void heapify(ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E,Integer> map, int index)
{
int left = (2*index) + 1;
while (left < priorityQueue.size())
{
int max=left;
int right = left+1;
if (right < priorityQueue.size())
{ // there is a right child
if (priorityComparator.compare(priorityQueue.get(right), priorityQueue.get(left)) < 0)
max = max + 1;
}
if (priorityComparator.compare(priorityQueue.get(index), priorityQueue.get(max)) > 0)
{
Element<P,E> temp = priorityQueue.get(index);
swap(priorityQueue,map,temp,index,max,left);
}
else
break;
}
}
protected static <P,E> boolean insert(ArrayList<Element<P, E>> priorityQueue, Element<P, E> element, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping)
{
if(mapping.containsKey(element.getElement()) == false)
{
priorityQueue.add(element);
mapping.put(element.getElement(), priorityQueue.size()-1);
sort(priorityQueue, priorityComparator, mapping, priorityQueue.size()-1);
return true;
}
else
return false;
}
protected static <P,E> ArrayList<Element<P,E>> heapSort(ArrayList<Element<P,E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping)
{
ArrayList<Element<P,E>> minimumHeap = new ArrayList<>();
while(priorityQueue.isEmpty() == false)
minimumHeap.add(BinaryHeap.extractMinimum(priorityQueue, priorityComparator, mapping));
return minimumHeap;
}
protected static <T,E> void changePriority(ArrayList<Element<T,E>> priorityQueue, Element<T, E> element, Element<T,E> newElementPriority, HashMap<E, Integer> map, Comparator<Element<T,E>> priorityComparator) throws NoSuchElementException
{
if(map.containsKey(element.getElement()) == false)
throw new NoSuchElementException();
int index = map.get(element.getElement());
boolean topDown = priorityComparator.compare(priorityQueue.get(index), newElementPriority) > 0;
priorityQueue.get(index).setPriority(newElementPriority.getPriority());
if(topDown)
sort(priorityQueue, priorityComparator, map, index);
else
heapify(priorityQueue, priorityComparator, map, index);
}
private static<P,E> void swap(ArrayList<Element<P, E>> priorityQueue, HashMap<E,Integer> map,Element<P, E> temp, int index, int max, int left)
{
map.replace(priorityQueue.get(index).getElement(), max);
map.replace(priorityQueue.get(max).getElement(), index);
priorityQueue.set(index, priorityQueue.get(max));
priorityQueue.set(max, temp);
index = max;
left = (2*index) + 1;
}
}
需要帮忙吗
# 1 楼答案
那里的
sort
方法通常被称为heapifyUp
或bubbleUp
或siftUp
。它与heapify
的不同之处在于,它将节点向上移动heapify
将节点向下移动到树上。其他人则调用向下移动节点的函数sink
,向上移动的函数称为swim
不管你叫它什么,它的工作方式非常简单:
添加项目时使用此方法。例如,给定这个堆:
您希望将值1添加到堆中。所以你把它放在数组中最左边最下面的位置。在这种情况下,作为5岁的孩子:
然后,将新节点与其父节点进行比较。自1<;5.交换节点:
节点索引仍然不是0(根),因此需要再次比较。1<;2.所以你再次交换:
现在你又有了一个有效的堆