在这里,我使用了一个 maxHeap 来将元素按排序顺序排列,这个堆是使用数组实现的。
max_size 是数组的大小,size 是当前存储在数组中的元素数。
- offer() - 在叶子位置插入元素并调用 shifUp() 方法。
- poll() - 为此返回数组的第一个元素。然后用它的一个叶子替换数组的第一个元素。然后在第一个元素上调用 shiftDown() 方法。数组中的第一个元素将始终具有最高优先级。
- peek() - 这里我们只返回数组的第一个元素。我们不删除它。
在泛型数组的情况下,还有两种我无法实现的方法。如果它是一个整数数组,就不会有问题。这两种方法是——
- remove(E e) - 从队列中删除一个元素。为此,我需要将 e 的优先级更改为无穷大,然后在 e 上调用 shiftUp() 方法。之后,我只需要调用 poll() 方法。
但我无法找到如何将通用元素的优先级更改为无穷大。如果它是一个整数,我会用 Integer.MAX_VALUE 替换后备数组中的元素。
- replace(E e1, E e2) - 在这里,我只需要删除元素 e1 并插入元素 e2。由于此方法调用 remove() 方法,我无法实现它。
_
import java.util.Comparator;
public class PriorityQueueUsingHeap<E>
{
private int size;
private Object H[];
public PriorityQueueUsingHeap(int max_size)
{
H = new Object[max_size];
}
private Comparator<E> comparator;
public PriorityQueueUsingHeap(int max_size, Comparator<E> comparator)
{
this.comparator = comparator;
H = new Object[max_size];
}
private E parent(int i)
{
return (E) H[(i - 1) / 2];
}
private E left(int i)
{
return (E) H[2 * i + 1];
}
private E right(int i)
{
return (E) H[2 * i + 2];
}
private boolean greaterThanOrEqualTo(E e1, E e2) // return e1>=e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) >= 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) >= 0;
}
}
private boolean lessThan(E e1, E e2) // return e1<e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) < 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) < 0;
}
}
private boolean lessThanOrEqualTo(E e1, E e2) // return e1<=e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) <= 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) <= 0;
}
}
private boolean greaterThan(E e1, E e2) // return e1>e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) > 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) > 0;
}
}
private void swap(int i1, int i2)
{
E temp = get(i1);
H[i1] = H[i2];
H[i2] = temp;
}
private E get(int i)
{
return (E) H[i];
}
private void shiftUp(int i)
{
while (i > 0 & greaterThanOrEqualTo(get(i), parent(i)))
{
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
private void shiftDown(int i)
{
int max_index = i;
if ((2 * i + 1) <= size-1 && lessThan(get(max_index), left(i)))
max_index = 2 * i + 1;
if (((2 * i + 2) <= size-1) && (lessThan(get(max_index), right(i))))
max_index = 2 * i + 2;
if (i != max_index)
{
swap(i, max_index);
shiftDown(max_index);
}
}
public void offer(E data)
{
if(size == H.length)
System.out.println("Queue is full");
else
{
H[size] = (E) data;
shiftUp(size);
size++;
}
}
public E peek()
{
return get(0);
}
public E poll()
{
if(size==0)
{
System.out.println("Queue is empty");
return null;
}
else
{
E result = get(0);
H[0] = H[size-1];
size--;
shiftDown(0);
return result;
}
}
public E remove(E e)
{
// Logic
return e;
}
public void replace(E e1, E e2)
{
offer(e2);
remove(e1);
}
}
这是相同的主要课程-
public class Main_PriorityQueueUsingHeap
{
public static void main(String[] args)
{
PriorityQueueUsingHeap<Integer> q1 = new PriorityQueueUsingHeap<>(10);
for (int i = 0; i < 5; i++)
{
q1.offer(i);
}
for (int i = 0; i < 5; i++)
{
System.out.print(q1.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<String> q2 = new PriorityQueueUsingHeap<>(10);
q2.offer("Jatin");
q2.offer("Ashvini");
q2.offer("Ram");
q2.offer("Mahesh");
q2.offer("Kamal");
for (int i = 0; i < 5; i++)
{
System.out.print(q2.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<String> q3 = new PriorityQueueUsingHeap<>(10,
(s1, s2) -> {
return (s1.length() != s2.length()) ? s1.length() - s2.length() : s1.compareTo(s2);
});
q3.offer("Jatin");
q3.offer("Ashvini");
q3.offer("Ram");
q3.offer("Mahesh");
q3.offer("Kamal");
for (int i = 0; i < 5; i++)
{
System.out.print(q3.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<Integer> q4 = new PriorityQueueUsingHeap<>(10);
q4.offer(12);
q4.offer(2);
q4.offer(42);
q4.offer(62);
q4.offer(12);
for (int i = 0; i < 5; i++)
{
System.out.print(q4.poll() + " ");
}
}
}
这是输出 -
4 3 2 1 0
Ram Mahesh Kamal Jatin Ashvini
Ashvini Mahesh Kamal Jatin Ram
62 42 12 12 2
主类说明 - 我创建了 4 个优先级队列并执行了以下操作:
- q1 :整数的通用队列。将整数 0 到 4 相加,然后逐个轮询元素。输出显示它们中的每一个都是按优先级降序排列的(数字越大,优先级越高)。
- q2 :没有给出比较器的字符串的通用队列。因此,将根据 Comparable 接口中的 compareTo(E e) 方法比较两个字符串。输出按字典顺序排序。
- q3 :带有比较器的字符串的通用队列。此比较器比较两个字符串的长度,如果它们相同,则按字典顺序对字符串进行排序。
- q4 :整数的通用队列。添加了一些随机数,并在逐个轮询时,所有这些都按优先级降序排列。由于没有通过比较器,因此优先级是根据 compareTo(E e) 方法决定的。