Là cây nhị phân hoàn hảo (có nghĩa là tất cả các tầng những được điền đủ, không tính tầng cuối, cùng tầng cuối cần có càng những thành phần bên trái càng tốt). Tính chất này giúp chúng ta rất có thể implement Binary Heap bằng cách áp dụng 1 mảng nhằm đựng nó.Binary Heap nên là Max Heap hoặc Min Heap. Trong Min Heap, phần tử nghỉ ngơi node phụ thân cần là bé dại rộng toàn bộ các thành phần sống node nhỏ. Max Heap tương tự như MinHeap.

Bạn đang xem: Heap là gì

Ví dụ Min Heap

10 10 / / đôi mươi 100 15 30 / / / 30 40 50 100 40

Biểu diễn Binary Heap

Binary Heap là 1 cây nhị phân hoàn hảo cho nên vì thế nó thường được trình diễn bên dưới dạng một mảng.

Root là Arr<0>.

Xem thêm: Phần Mềm Tạo Logo Sinhvienit, Eximioussoft Logo Designer Pro 3

Với mỗi Arr trong mảng

Arr < (i - 1) / 2 >Là node cha
Arr < (2i) + 1 >Là node bé mặt trái
Arr < (2i) + 2 >Là node con bên phải

*

class MaxHeap attr_accessor :arr def initialize
arr = <> end def swap(a, b) temp = arr arr = arr arr = temp kết thúc def parent i (i - 1) / 2 over def left i i * 2 + 1 kết thúc def right i i * 2 + 2 over def extractMax root = arr<0> arr<0> = arr arr.pop() MaxHeapify(0) return root end def deleteKey i arr = MIN_INT # gán bằng min rồi gửi lên cội while i != 0 và arr arr swap(i, parent(i)) i = parent(i) over # sau đó xóa extractMax() end def insertKey k arr.push(k) # chuyển vào cuối mảng # sau đó thu xếp lại trang bị từ bỏ i = arr.length - 1 while i != 0 và arr arr vì chưng swap(i, parent(i)) i = parent(i); kết thúc end def MaxHeapify i # bảo đảm những node từ node i->n đều phải có đặc điểm 2 l = left(i) r = right(i) largest = i if l arr.length & arr > arr largest = l kết thúc if r arr.length và arr > arr largest = r kết thúc if largest != i swap(i, largest) MaxHeapify(largest) kết thúc endendHeapSortHeap sort là 1 kỹ thuật sắp xếp dựa trên cấu trúc tài liệu Binary Heap. Nó tựa như nhỏng thu xếp chọn lựa trong số ấy trước tiên chúng ta search thành phần lớn số 1 (hoặc nhỏ dại nhất) và đặt thành phần kia sống cuối (hoặc đầu, tùy ý).

Heap Sort mang đến sắp xếp từ nhỏ tuổi cho lớn

Tạo Max Heap chứa toàn bộ bộ phận phải sắp đến xếpHiện nay, bộ phận lớn nhất nằm ở vị trí root của heap, thay đổi nơi nó về cuối mảng, giảm kích thước của heap đi 1, kế tiếp heapify lại heap bỏ qua thành phần cuối mảng.Lặp lại bước 2 cho đến không còn heap.

def swap(arr, a, b) temp = arr arr = arr arr = tempenddef heapify arr, n, i l = 2*i + 1 # left child"s position r = 2*i + 2 # right child"s position largest = i if l n và arr > arr largest = l kết thúc if r n and arr > arr largest = r kết thúc if largest != i swap(arr, i, largest) heapify(arr, n, largest) endenddef heapSort arr, n # trước tiên bắt buộc heapify mang lại đúng tính chất 2 (thành phần thân phụ to hơn bộ phận con) # bắt đầu từ bỏ tầng gần cuối, bởi vì tầng cuối ko bao gồm con. for i in (n/2 - 1).downto(0) heapify(arr, n, i) over # rước phần tử lớn nhất của heap (tức arr<0>) thay đổi địa điểm về cuối mảng rồi ko quyên tâm đến nó nữa # kế tiếp heapify lại heap(hôm nay số lượng bộ phận trong heap đang giảm đi 1) # tái diễn đến khi heap còn 1 phần tử for i in (n-1).downto(0) swap(arr, 0, i); heapify(arr, i, 0); endend

*
Heap sort là một trong thuật toán sắp xếp trên vị trí.Độ phức hợp của heapify là O(logn), độ phức hợp của vấn đề tạo nên với build heap là O(n). Vậy buộc phải độ phức tạp của heap sort là O(nlogn)

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *