Heap Sort là kỹ thuật sắp xếp dựa trên cấu trúc dữ liệu heap nhị phân. Để tiến hành sắp xếp heap, bạn cần phải làm quen với cây nhị phân và heap nhị phân.
Cây nhị phân hoàn chỉnh là gì?
Một cây nhị phân hoàn chỉnh là một cấu trúc dữ liệu dạng cây trong đó tất cả các cấp ngoại trừ cấp cuối cùng được lấp đầy hoàn toàn. Mức cuối cùng phải được điền từ phía bên trái.
Binary heap là gì?
Binary heap là một trường hợp đặc biệt của cây nhị phân. Các đống nhị phân có hai loại -
-
Max Heap - Nút cha ở mỗi cấp lớn hơn các nút con của nó.
-
Min Heap - Nút cha ở mỗi cấp nhỏ hơn các nút con của nó.
Biểu diễn mảng của cây nhị phân hoàn chỉnh
Heap nhị phân có thể được biểu diễn dưới dạng một mảng vì nó hiệu quả về không gian. Nếu nút cha được lưu trữ ở chỉ mục I, nút con bên trái có thể được tính bằng 2 * i + 1 và nút con bên phải bằng 2 * i + 2. Giả sử, chỉ mục bắt đầu từ 0.
Thuật toán sắp xếp đống
-
Tạo đống tối đa từ một cây nhị phân hoàn chỉnh.
-
Xóa gốc và thay thế nó bằng phần tử cuối cùng trong heap, giảm kích thước của heap đi 1 và lại tạo một heap tối đa từ các nút còn lại.
-
Lặp lại bước 2 cho đến khi chúng ta chỉ còn 1 nút.
Tạo đống tối đa từ một cây nhị phân hoàn chỉnh
Đây là mã để xây dựng đống tối đa từ một cây nhị phân hoàn chỉnh, trong đó hai nút con được so sánh với nút gốc. Nếu phần tử Lớn hơn không phải là phần tử gốc, thì hãy hoán đổi phần tử lớn hơn với phần tử gốc. Đây là một thủ tục đệ quy. Gốc hiện tại nhỏ hơn các nút con của nó liên tục được so sánh với các cây con thấp hơn của nó trừ khi nó đến đúng vị trí của nó.
Đoạn mã sau tạo một đống tối đa từ một cây nhị phân hoàn chỉnh, về cơ bản là mảng mà chúng ta muốn sắp xếp.
def heapify(arr, n, i): # Find largest among root and children 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 root is not largest, swap with largest and continue heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
Sắp xếp đống
Tại thời điểm này, chúng tôi có đống tối đa với chúng tôi. Bây giờ chúng ta cần làm những việc sau.
-
Trao đổi phần tử gốc với phần tử cuối cùng trong heap.
-
Giảm kích thước của đống đi 1 (Điều này có nghĩa là phần tử lớn nhất đã đạt đến vị trí cuối cùng, chúng tôi không cần xem xét phần tử đó).
-
Tạo lại đống tối đa loại trừ phần tử cuối cùng.
-
Lặp lại các bước trên cho đến khi chúng ta chỉ còn lại 1 phần tử.
for i in range(n-1, 0, -1): # Swap arr[i], arr[0] = arr[0], arr[i] # Heapify root element heapify(arr, i, 0)
Chương trình hoàn chỉnh để sắp xếp đống bằng Python như sau -
def heapify(arr, n, i):
# Find largest among root and children
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 root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ') TÍNH HỢP LÍ CỦA THỜI GIAN - O (n logn)