Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
2.0 kB
4
Indexable
Never
package LinkList_Stack_Queue;

public class Queue {
	public class Task { // biểu diễn node Task
		String job; // tên công việc
		int priority; // mức độ ưu tiên

		public Task(String job, int priority) { // constructor của lớp
			this.job = job;
			this.priority = priority;
		}

		public String toString() { // phương thức toString
			return "Job Name : " + job + "\nPriority : " + priority;
		}
	}

	public class PriorityQueue { // định nghĩa hàng đợi ưu tiên
		protected Task[] heap; // mảng các Job với độ ưu tiên
		protected int heapSize, capacity; // kích cỡ và kích thước tối đa

		public PriorityQueue(int capacity) { // constructor của lớp
			this.capacity = capacity + 1;
			heap = new Task[this.capacity];
			heapSize = 0;
		}

		public void clear() { // loại bỏ hàng đợi ưu tiên
			heap = new Task[capacity];
			heapSize = 0;
		}

		public boolean isEmpty() {
			return heapSize == 0;
		} // kiểm tra tính rỗng

		public boolean isFull() { // kiểm tra tính đầy
			return heapSize == (capacity - 1);
		}

		public int size() { // lấy kích cỡ
			return heapSize;
		}

		public void Push(String job, int priority) {
			Task newJob = new Task(job, priority);
			this.heap[++this.heapSize] = newJob;
			int pos = heapSize;
			while (pos != 1 && newJob.priority > heap[pos / 2].priority) {
				heap[pos] = heap[pos / 2];
				pos /= 2;
			}
			heap[pos] = newJob;
		}

		public Task Pop() {
			int parent, child;
			Task item, temp;
			if (isEmpty()) {
				System.out.println("Heap bị rỗng");
				return null;
			}
			item = heap[1];
			temp = heap[heapSize--];
			parent = 1;
			child = 2;
			while (child <= heapSize) {
				if (child < heapSize && heap[child].priority < heap[child + 1].priority)
					child++;
				if (temp.priority >= heap[child].priority)
					break;
				heap[parent] = heap[child];
				parent = child;
				child *= 2;
			}
			heap[parent] = temp;
			return item;
		}
	}

}