时间戳

首页 > 解决方案 > 了解优先队列中的 SORT 方法

java - 了解优先队列中的 SORT 方法

问题描述

我有一个我同学写的代码。

问题是我无法理解SORT METHOD的作用。

据我所知，它命令优先级队列没有被修改。相反，heapify 方法是一种有助于操作堆（在本例中为 MIN HEAP）的方法，它允许元素 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;
}
}

请提供任何帮助

标签： javaheappriority-queue

解决方案

那里的sort方法通常称为heapifyUporbubbleUp或siftUp。它的不同之处heapify在于它将节点向上移动。heapify将节点沿树向下移动。其他人调用向下移动节点的函数，调用向上移动sink的函数swim。

不管你怎么称呼它，它的工作方式都非常简单：

while node_index > 0
    if the node is smaller than its parent
      swap the node with its parent
      node_index = parent_index

添加项目时使用此方法。例如，给定这个堆：

    2
 3     5
4 7   6

您想将值 1 添加到堆中。所以你把它放在数组中最低、最左边的位置。在这种情况下，作为 5 的右孩子：

    2
 3     5
4 7   6 1

然后，将新节点与其父节点进行比较。由于 1 < 5，您交换节点：

    2
 3     1
4 7   6 5

节点索引仍然不是0（根），所以你再比较一下。1 < 2，所以你再次交换：

    1
 3     2
4 7   6 5

现在你又拥有了一个有效的堆。

推荐阅读