Bài viết này sẽ cung cấp cho bạn một cái nhìn tổng quan đầy đủ về hoạt động của heap sort và sau đó chúng ta sẽ học cách triển khai Binary Heap trong Java.
con rối và đầu bếp là gì
Đây là chương trình làm việc cho bài viết này:
Hãy bắt đầu nào!
Sắp xếp theo đống là gì?
Heap về cơ bản là một cấu trúc dữ liệu dựa trên cây. Nó có các nút. Nút bao gồm các phần tử nhất định. Mỗi nút chứa một phần tử.
Các nút có thể có con. Nếu trường hợp không có con thì gọi là Lá.
Có hai quy tắc cần tuân theo:
- Giá trị của mọi nút phải nhỏ hơn hoặc bằng tất cả các giá trị được lưu trữ trong các nút con của nó.
- Nó có chiều cao ít nhất có thể.
Heaps cực kỳ hiệu quả trong việc giải nénphần tử nhỏ nhất hoặc lớn nhất.
Hãy chuyển sang min heap ngay bây giờ!
Min Heap
Min heap là một cây nhị phân hoàn chỉnh trong đó giá trị của phần tử gốc nhỏ hơn hoặc bằng một trong hai phần tử con.
Biểu diễn của min heap
Arr [(i-1) / 2]: điều này sẽ trả về nút cha.
tìm số lớn nhất trong java
Arr [(2 * i) + 1]: điều này sẽ trả về nút con bên trái.
Arr [(2 * i) + 2]: điều này sẽ trả về nút con bên phải.
Có một số phương pháp của Min Heap:
- chèn(): Một khóa mới ở cuối cây được thêm vào. Trong trường hợp khóa mới lớn hơn khóa cha thì không cần làm gì cả, còn lại, chúng ta phải tra cứu để thiết lập thuộc tính heap.
- getMin (): phương thức này giúp trả về phần tử gốc.
- extractMin (): phương thức này trả về giá trị tối thiểuthành phần.
Chuyển sang Max heap ngay bây giờ.
Đống tối đa
Max heap là một cây nhị phân hoàn chỉnh trong đó giá trị của phần tử gốc lớn hơn hoặc bằng một trong hai phần tử con.
Max heap cũng bao gồm một số phương thức!
- Chèn (): nó sẽ chèn một phần tử trong heap.
- Xóa bỏ() : nó sẽ xóa một phần tử khỏi heap.
- FindMax (): nó sẽ tìm phần tử tối đa từ đống.
- printHeap (): Nó sẽ in nội dung của đống
Bây giờ hãy để tôi chỉ cho bạn cách triển khai heap thông qua một sơ đồ và sau đó là Javamã.
Triển khai đống trong Java
Biểu đồ:
làm thế nào để chuyển đổi một double thành một int
Sơ đồ trên cho thấy heap nhị phân trong Java. Như bạn đã biết rằng có hai heap: Min heap và Max heap, đây là sơ đồ:
Bây giờ, chuyển sang phân đoạn tiếp theo, chúng ta sẽ xem cách triển khai một đống nhị phân trong Java.
Mã:
public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Điều này sẽ khởi tạo heap của chúng ta với kích thước mặc định. * / public BinaryHeap (int dung lượng) {heapSize = 0 heap = new int [Capacity + 1] Arrays.fill (heap, -1)} / ** * Điều này sẽ kiểm tra xem heap có trống hay không * Độ phức tạp: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Điều này sẽ kiểm tra xem heap đã đầy hay chưa * Độ phức tạp: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Thao tác này sẽ chèn phần tử mới vào heap * Độ phức tạp: O (log N) * Trong trường hợp xấu nhất, chúng ta cần phải duyệt đến gốc * / public void insert (int x) {if (isFull ()) ném NoSuchElementException mới ('Heap đã đầy, không có chỗ để chèn new element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Thao tác này sẽ xóa phần tử tại chỉ mục x * Độ phức tạp: O (log N) * * / public int delete (int x) {if (isEmpty ()) ném NoSuchElementException mới ('Heap trống, Không có phần tử nào để xóa') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Phương thức này được sử dụng để duy trì thuộc tính heap trong khi chèn một phần tử. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Phương thức này được sử dụng để duy trì thuộc tính heap trong khi xóa một phần tử. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Phương thức này được sử dụng để in tất cả phần tử của heap * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 iVới điều này, chúng ta đến phần cuối của bài viết này về Binary Heap trong Java. Kiểm tra của Edureka, một công ty học trực tuyến đáng tin cậy với mạng lưới hơn 250.000 người học hài lòng trải dài trên toàn cầu. Khóa đào tạo và cấp chứng chỉ về Java J2EE và SOA của Edureka được thiết kế cho sinh viên và các chuyên gia muốn trở thành Nhà phát triển Java. Khóa học được thiết kế để cung cấp cho bạn khởi đầu về lập trình Java và đào tạo bạn về cả khái niệm Java cốt lõi và nâng cao cùng với các khung Java khác nhau như Hibernate & Spring.
Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần nhận xét của blog “Java ArrayList” này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.