우선 순위 대기열 클래스에서 remove 메소드가 있습니다. 할당을 위해 처음부터 만들었습니다. 내가 만든 우선 순위 큐는 0에서 시작하는 배열로 배열에 보관됩니다. 배열 길이와 동일한 크기를 추적합니다. 제거 방법은 자격이 도우미 메서드를 사용D- 힙 우선 순위 대기열에서 가장 작은 하위를 찾는 방법을 구현하는 방법
부모가 부모가 저장되는 배열의 위치를, 그리고 내가 그 작은 아이를 반환 찾고public int findSmallest(int parent)
. 순서는 잎이 아닌 각 노드에있는 자식 수입니다. 내 findSmallest의 코드는 :
import java.util.*;
public class PriorityQueue {
private class Item {
private int priority;
private Object data;
private Item(int p, Object d) {
priority = p;
data = d;
}
}
private Item queue[];
private int order;
private int size;
public PriorityQueue(int ord, int s) {
queue = new Item[s];
order = ord;
size = 0;
}
public int getPriority() {
if (size > 0) {
return queue[0].priority;
}
// -55 signifies that the queue is empty
return -55;
}
public Object getData() {
if (size > 0) {
return queue[0].priority;
}
return null;
}
public void remove() {
if (empty() == true) {
System.out.println("Queue is empty, there is nothing to remove.");
return;
}
Item x = queue[size - 1];
size--;
int child = 1;
int parent = 0;
while (child <= size) {
child = findSmallest(parent);
for (int i = order * parent + 1; i < child + order; i++) {
if (child < size && queue[i].priority < queue[child].priority)
child = i;
}
if (x.priority < queue[child].priority)
break;
else {
parent = child;
queue[(child - 1)/order] = queue[child];
child = order * child + 1;
}
}
queue[(child - 1)/order] = x;
}
public int findSmallest(int parent) {
int child = parent * order + 1;
int smallest = child;
for (int i = child; i < order + child; ++i) {
if (size >= i) {
return child;
}
if (queue[i].priority <= queue[smallest].priority) {
smallest = child;
}
}
return child;
}
public int getSize() {
return size;
}
public boolean full() {
return size == queue.length;
}
public boolean empty() {
if (size > 0) {
return false;
}
return true;
}
public void insert(int p, Object d) {
// 1. Create a new Item and add it to queue[size]
// Somewhere store new node created as TEMP
// 2. while loop
// 3. check if node has parent
// 4. if it does --> check if parent.priority > child.priority
// 5. if yes, swap
if (full() == true) {
System.out.println("Queue is full, cannot add new node.");
return;
}
queue[size] = new Item(p, d);
sort();
size++;
}
// Sort() swaps new child node with parents if child.priority < parent.priority
public void sort() {
int child = size;
Item temp = queue[child];
while (child > 0 && queue[child].priority < queue[(child-1)/(order)].priority) {
queue[child] = queue[(child-1)/order];
queue[(child-1)/order] = temp;
child = ((child - 1)/order);
}
queue[child] = temp;
}
public static void main(String[] args) {
PriorityQueue p1 = new PriorityQueue(5, 100);
PriorityQueue p2 = new PriorityQueue(6, 100);
PriorityQueue p3 = new PriorityQueue(7, 100);
int p = -1; //pointless initialization to keep the compiler happy
p1.insert(0, new Integer(0));
System.out.println("First insert");
for (int i = 1; i < 100; i++)
p1.insert(i, new Integer(i));
for (int i = 0; i < 100; i++)
p2.insert(i, new Integer(i));
for (int i = 0; i < 100; i++)
p3.insert(i, new Integer(i));
System.out.println("First insert tests");
System.out.print(p1.getPriority()+",");
while (!p1.empty()) {
p = p1.getPriority();
Object d = p1.getData();
p1.remove();
}
System.out.println(p);
System.out.print(p2.getPriority()+",");
while (!p2.empty()) {
p = p2.getPriority();
Object d = p2.getData();
p2.remove();
}
System.out.println(p);
System.out.print(p3.getPriority()+",");
while (!p3.empty()) {
p = p3.getPriority();
Object d = p3.getData();
p3.remove();
}
System.out.println(p);
System.out.println("First Remove Test");
for (int i = 100; i > 0 ; i--)
p1.insert(i, new Integer(i));
for (int i = 100; i > 0 ; i--)
p2.insert(i, new Integer(i));
for (int i = 100; i > 0 ; i--)
p3.insert(i, new Integer(i));
System.out.println("Second insert tests");
System.out.print(p1.getPriority()+",");
while (!p1.empty()) {
p = p1.getPriority();
Object d = p1.getData();
p1.remove();
}
System.out.println(p);
System.out.print(p2.getPriority()+",");
while (!p2.empty()) {
p = p2.getPriority();
Object d = p2.getData();
p2.remove();
}
System.out.println(p);
System.out.print(p3.getPriority()+",");
while (!p3.empty()) {
p = p3.getPriority();
Object d = p3.getData();
p3.remove();
}
System.out.println(p);
System.out.println("Second Remove Test");
Random r1 = new Random(1000);
while (!p3.full()) {
p = r1.nextInt(200);
System.out.print(p+",");
p3.insert(p, new Integer(p));
}
System.out.println();
while (!p3.empty()) {
System.out.print(p3.getPriority()+",");
Object d = p3.getData();
p3.remove();
}
System.out.println();
System.out.println("Third Remove Test");
}
}
주요 내 코드를 테스트하고 3 가지 방법이 포함되어
public int findSmallest(int parent) {
int child = parent * order + 1;
int smallest = child;
for (int i = child; i < order + child; ++i) {
if (size >= i) {
return child;
}
if (queue[i].priority <= queue[smallest].priority) {
smallest = child;
}
}
return child;
}
은 현재 PriorityQueue 인 클래스의 완전한 구현은 내가 만든 경계 예외 밖으로 배열입니다. 문제는 바로 findSmallest
방법 인 경우
전체 구현을 게시 할 수 있습니까? – davidbuzatto
업데이트 됨, 고맙습니다. –
살펴 보겠습니다. 기다려주십시오. – davidbuzatto