Trước khi chúng ta bắt đầu, giả sử rằng bạn đã biết về Cây nhị phân (trong cây nhị phân, mỗi nút lưu trữ một khóa lớn hơn tất cả các khóa trong cây con bên trái của nó và nhỏ hơn tất cả các khóa trong cây con bên phải của nó ) . Trong khi đó, Heap nhị phân là một cây nhị phân hoàn chỉnh thỏa mãn thuộc tính sắp xếp heap tối thiểu hoặc heap tối đa. Nếu bạn không quen thuộc với những khái niệm này, chúng tôi khuyên bạn nên hiểu những khái niệm này như một điều kiện tiên quyết. Nhiều lập trình viên mới làm quen có thể gặp khó khăn với khái niệm Heaps, Min Heaps và Priority Queues. Trong bài đăng này, chúng ta sẽ tìm hiểu sâu để xem heap khác với Min-Heap như thế nào và cách chúng ta có thể sử dụng Hàng đợi ưu tiên để triển khai Heap tối thiểu.
Min Heap là gì?
Một min-heap có thuộc tính là mọi nút ở cấp 'n' đều lưu trữ một giá trị nhỏ hơn hoặc bằng giá trị của các nút con của nó ở cấp 'n+1'. Vì gốc có giá trị nhỏ hơn hoặc bằng với các con của nó, nên gốc có giá trị nhỏ hơn hoặc bằng với các con của chúng, nên gốc lưu trữ giá trị nhỏ nhất trong tất cả các giá trị trong cây.
Ví dụ
Hình 1: Một đống tối thiểu đơn giản
Lưu ý rằng không có mối quan hệ cần thiết giữa giá trị của một nút và giá trị của anh chị em của nó trong heap tối thiểu hoặc heap tối đa. Ví dụ, có thể các giá trị cho tất cả các nút trong cây con bên trái của gốc lớn hơn các giá trị cho mọi nút của cây con bên phải.
Hình 2: Heap tối thiểu với các nút con bên trái > các nút con bên phải
Biểu diễn của Min Heap trong Java
Cấu trúc dữ liệu được sử dụng phổ biến nhất để biểu diễn Min Heap là một Mảng đơn giản. Là người mới bắt đầu, bạn không cần phải nhầm lẫn giữa "mảng" với "đống nhỏ". Bạn có thể xem nó như là, các giá trị của các nút/phần tử của một đống nhỏ được lưu trữ trong một mảng . Giống như việc chúng ta không có bất kỳ cấu trúc dữ liệu nào để lưu trữ một “ cây ” trong Java và chúng ta xây dựng một “nút” cho nó hoặc cách chúng ta sử dụng “bản đồ” để lưu trữ một “ đồ thị ”.
Hình 3: Biểu diễn mảng của Heap trong Hình 2
Chúng tôi sẽ trình bày cách bạn có thể truy cập nút cha, nút con bên phải hoặc bên trái một cách đơn giản bằng cách sử dụng các công thức sau.
Đặt minHeap[] là một mảng số nguyên có gốc tại chỉ số “ i = 0; ”.
minHeap[(i - 1)/2] trả về nút cha.
minHeap[(i * 2) + 2] trả về nút con bên phải.
minHeap[(i * 2) + 1] trả về nút con bên trái.
Xem xét Hình # 2 được đưa ra ở trên, giá trị của root (parent) = 3, nút con bên trái là 13 và nút con bên phải = 7.
Triển khai Min Heap trong Java - Sử dụng Mảng
Hãy xem cách triển khai cơ bản của Heaps bằng cách sử dụng mảng, với chỉ mục là vị trí hiện tại của phần tử sẽ được thêm vào và kích thước là tổng kích thước của mảng.
import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
đầu ra
Heap tối thiểu là: [3, 13, 7, 16, 21, 12, 9]
Cha mẹ : 3 Trái : 13 Phải :7
Cha mẹ : 13 Trái : 16 Phải :21
Phụ huynh : 7 Trái : 12 Phải : 9
Giá trị tối thiểu là: 3
Heap tối thiểu là: [7, 13, 9, 16, 21, 12, 9] // sau khi xóa gốc
Cha mẹ : 7 Trái : 13 Phải :9
Cha mẹ : 13 Trái : 16 Phải :21
Phụ huynh : 9 Còn lại : 12
hàng đợi ưu tiên
Hàng đợi ưu tiên là một loại hàng đợi đặc biệt trong đó mỗi phần tử được liên kết với một mức độ ưu tiên và được đặt theo mức độ ưu tiên của nó. Để triển khai heap tối thiểu dễ dàng hơn, chúng tôi sử dụng lớp PriorityQueue java.util.PriorityQueue do Java cung cấp. Nếu các yếu tố đã cho được cho là sắp xếp/đặt ở mức ưu tiên thì Hàng đợi ưu tiên sẽ được sử dụng. Hàng đợi ưu tiên khác với Hàng đợi đơn giản vì hàng đợi tiêu chuẩn tuân theo thuật toán Nhập trước - Xuất trước ( FIFO ), nhưng đôi khi các phần tử của hàng đợi cần được xử lý theo mức độ ưu tiên, đó là lý do Hàng đợi ưu tiên được thiết kế. Khi bạn thêm các phần tử vào hàng đợi ưu tiên, một đống tối thiểu được tạo theo mặc định.
Hoạt động chung
Trước khi chúng ta chuyển sang phần triển khai, đây là một vài thao tác phổ biến trong java.util.PriorityQueue mà bạn cần biết.
add(int element) chèn phần tử đã chỉ định vào hàng đợi ưu tiên.
remove(int element) xóa một phiên bản duy nhất của phần tử đã chỉ định khỏi hàng đợi này, nếu nó hiện diện.
peek() truy xuất nhưng không xóa phần đầu của hàng đợi này hoặc trả về null nếu hàng đợi trống.
poll() truy xuất và xóa phần đầu của hàng đợi này hoặc trả về null nếu hàng đợi này trống.
contains() trả về “true” nếu hàng đợi này chứa phần tử đã chỉ định.
size() trả về số phần tử trong hàng đợi ưu tiên này/minheap.
Triển khai Min Heap trong Java bằng Hàng đợi ưu tiên
Đây là cách bạn có thể triển khai một đống tối thiểu bằng cách sử dụng lớp hàng đợi ưu tiên của java.
import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
Các đống nhỏ nhất được sử dụng rộng rãi để truy xuất phần tử nhỏ nhất trong một nhóm các phần tử trong thời gian không đổi. Có rất nhiều ứng dụng khác của cấu trúc dữ liệu này, tuy nhiên bạn có thể chọn bất kỳ phương pháp nào để thực hiện điều này. Không cần phải nói, bạn phải thực hành với sự kiên nhẫn để thành thạo nó. Vì vậy, hãy vận động cơ bắp của chúng ta và bắt đầu làm việc!
Oleksandr became interested in programming at school, and he wrote games. Later, this hobby grew into professional development. Af ...
[Đọc toàn bộ tiểu sử]
GO TO FULL VERSION