Cấu trúc dữ liệu đống

Trong hướng dẫn này, bạn sẽ tìm hiểu cấu trúc dữ liệu heap là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về hoạt động đống trong C, C ++, Java và Python.

Cấu trúc dữ liệu Heap là một cây nhị phân hoàn chỉnh thỏa mãn thuộc tính heap . Nó cũng được gọi là một đống nhị phân .

Cây nhị phân hoàn chỉnh là một cây nhị phân đặc biệt trong đó

  • mọi cấp độ, ngoại trừ có thể là cấp độ cuối cùng, đều được lấp đầy
  • tất cả các nút càng xa càng tốt

Thuộc tính Heap là thuộc tính của một nút trong đó

  • (cho tối đa heap) khóa của mỗi nút luôn lớn hơn / s nút con của nó và khóa của nút gốc là lớn nhất trong số tất cả các nút khác;
  • (cho min heap) khóa của mỗi nút luôn nhỏ hơn / s nút con và khóa của nút gốc là nhỏ nhất trong số tất cả các nút khác.

Hoạt động đống

Một số hoạt động quan trọng được thực hiện trên một đống được mô tả bên dưới cùng với các thuật toán của chúng.

Heapify

Heapify là quá trình tạo cấu trúc dữ liệu heap từ cây nhị phân. Nó được sử dụng để tạo Min-Heap hoặc Max-Heap.

  1. Hãy để mảng đầu vào là
  2. Tạo một cây nhị phân hoàn chỉnh từ mảng
  3. Bắt đầu từ chỉ mục đầu tiên của nút không phải lá có chỉ mục được cho bởi n/2 - 1.
  4. Đặt phần tử hiện tại ilà largest.
  5. Chỉ số của con bên trái được cho bởi 2i + 1và con bên phải được cho bởi 2i + 2.
    Nếu leftChildlớn hơn currentElement(nghĩa là phần tử ở ithchỉ mục), đặt leftChildIndexlà lớn nhất.
    Nếu rightChildlớn hơn phần tử trong largest, hãy đặt rightChildIndexlà largest.
  6. Trao đổi largestvớicurrentElement
  7. Lặp lại các bước 3-7 cho đến khi các cây con cũng được xếp thành đống.

Thuật toán

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Để tạo Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Đối với Min-Heap, cả hai leftChildvà rightChildphải nhỏ hơn cha cho tất cả các nút.

Chèn phần tử vào Heap

Thuật toán chèn trong Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Chèn phần tử mới vào cuối cây.
  2. Làm nặng cây.

Đối với Min Heap, thuật toán trên được sửa đổi để parentNodeluôn nhỏ hơn newNode.

Xóa phần tử khỏi đống

Thuật toán xóa trong Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Chọn phần tử sẽ bị xóa.
  2. Trao đổi nó với phần tử cuối cùng.
  3. Loại bỏ phần tử cuối cùng.
  4. Làm nặng cây.

Đối với Min Heap, thuật toán trên được sửa đổi để cả hai childNodesđều lớn hơn nhỏ hơn currentNode.

Peek (Tìm tối đa / phút)

Phép toán Peek trả về phần tử lớn nhất từ ​​Max Heap hoặc phần tử tối thiểu từ Min Heap mà không xóa nút.

Đối với cả Max heap và Min Heap

 trả về rootNode

Extract-Max / Min

Extract-Max trả về nút có giá trị lớn nhất sau khi xóa nó khỏi Max Heap trong khi Extract-Min trả về giá trị tối thiểu cho nút sau khi xóa nó khỏi Min Heap.

Ví dụ về Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java import java.util.ArrayList; class Heap ( void heapify(ArrayList hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Ứng dụng cấu trúc dữ liệu đống

  • Heap được sử dụng trong khi triển khai hàng đợi ưu tiên.
  • Thuật toán Dijkstra
  • Sắp xếp đống

thú vị bài viết...