如何更改优先队列中的添加顺序

Question

我一直在研究优先级队列，但遇到了问题。我有一个字符串，我将这个字符串中的字母及其频率作为节点添加到优先级队列中。当我从我的优先级队列中拉出一个节点时，我得到了频率最高的节点。但我想要最低的。我怎样才能做到这一点？如果您能提供帮助，我将不胜感激。

这是我自定义的 PriorityQueue Class:

class PriorityQueue
{
    private Node[] heap;
    private int heapSize, capacity;

    /** Constructor **/
    public PriorityQueue(int capacity)
    {
        this.capacity = capacity + 1;
        heap = new Node[this.capacity];
        heapSize = 0;
    }
    /** function to clear **/
    public void clear()
    {
        heap = new Node[capacity];
        heapSize = 0;
    }
    /** function to check if empty **/
    public boolean isEmpty()
    {
        return heapSize == 0;
    }
    /** function to check if full **/
    public boolean isFull()
    {
        return heapSize == capacity - 1;
    }
    /** function to get Size **/
    public int size()
    {
        return heapSize;
    }
    public boolean isIncluded(Node element){
        if(isEmpty())
            return false;
        for(int i = 1; i<=heapSize; i++){
            if(heap[i].character == element.character){
                return true;
            }
        }
        return false;
    }
    /** function to insert task **/
    public void add(char character, int frequency)
    {
        Node newElement = new Node(frequency, character);
        if(!isIncluded(newElement)){
            heap[++heapSize] = newElement;
            int pos = heapSize;
            while (pos != 1 && newElement.freq > heap[pos/2].freq)
            {
                heap[pos] = heap[pos/2];
                pos /=2;
            }
            heap[pos] = newElement;
        }
    }
    /** function to remove task **/
    public Node poll()
    {
        int parent, child;
        Node item, temp;
        if (isEmpty() )
        {
            System.out.println("Heap is empty");
            return null;
        }

        item = heap[1];
        temp = heap[heapSize--];

        parent = 1;
        child = 2;
        while (child <= heapSize)
        {
            if (child < heapSize && heap[child].freq < heap[child + 1].freq)
                child++;
            if (temp.freq >= heap[child].freq)
                break;

            heap[parent] = heap[child];
            parent = child;
            child *= 2;
        }
        heap[parent] = temp;

        return item;
    }
}

这是我的主要测试 class:

import java.util.Scanner;
import java.util.Stack;

public class Main {
    static final int SIZE = 256;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        PriorityQueue pq = new PriorityQueue(256);
        Stack<Node> myStack = new Stack<>();

        System.out.print("Enter your message: ");
        String input = scanner.nextLine();

        detectCharWithFreq(input,pq);

        for (int i = 0; i < pq.size();) {
            Node newNode = pq.poll();
            System.out.println("Character: " + newNode.character + " Freq: " + newNode.freq);
        }
    }

    static void detectCharWithFreq(String str, PriorityQueue pq)
    {
        int sizeOfString = str.length();
        int[] freq = new int[SIZE];

        for (int i = 0; i < sizeOfString; i++)
            freq[str.charAt(i)]++;

        for (int i = 0; i < sizeOfString; i++) {
            int frequency = freq[str.charAt(i)];
            char character = str.charAt(i);

            if (frequency != 0) {
                pq.add(character,frequency);
                frequency = 0;
            }
        }
    }
}

这是我的输出：

"C:\Program Files\Java\jdk-15.0.1\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2020.3.1\lib\idea_rt.jar=55573:C:\Program Files\JetBrains\IntelliJ IDEA 2020.3.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\ayber\Desktop\Huffman\out\production\Huffman Main
Enter your message: hello
Character: l Freq: 2
Character: o Freq: 1
Character: h Freq: 1
Character: e Freq: 1

Process finished with exit code 0

我想要的输出：

"C:\Program Files\Java\jdk-15.0.1\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2020.3.1\lib\idea_rt.jar=55573:C:\Program Files\JetBrains\IntelliJ IDEA 2020.3.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\ayber\Desktop\Huffman\out\production\Huffman Main
Enter your message: hello
Character: o Freq: 1
Character: h Freq: 1
Character: e Freq: 1
Character: l Freq: 2

Process finished with exit code 0

Answer 1

你只需要扭转你的条件。如果有多个相同的频率，结果可能会有所不同，频率将按升序排列。

    public void add(char character, int frequency) {
        Node newElement = new Node(frequency, character);
        if (!isIncluded(newElement)) {
            heap[++heapSize] = newElement;
            int pos = heapSize;
            while (pos != 1 && newElement.freq < heap[pos / 2].freq) {  // ***HERE***
                heap[pos] = heap[pos / 2];
                pos /= 2;
            }
            heap[pos] = newElement;
        }
    }
    
    /** function to remove task **/
    public Node poll() {
        int parent, child;
        Node item, temp;
        if (isEmpty()) {
            System.out.println("Heap is empty");
            return null;
        }
        
        item = heap[1];
        temp = heap[heapSize--];
        
        parent = 1;
        child = 2;
        while (child <= heapSize) {
            if (child < heapSize
                    && heap[child].freq >= heap[child + 1].freq)  // ***HERE***
                child++;
            if (temp.freq < heap[child].freq)                     // and ***HERE***
                break;
            
            heap[parent] = heap[child];
            parent = child;
            child *= 2;
        }
        heap[parent] = temp;
        
        return item;
    }
}

如何更改优先队列中的添加顺序

How can I change the add order in my Priority Queue

java

data-structures

queue

priority-queue