ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง
แจ้งปัญหา − เราได้รับอาร์เรย์ เราต้องจัดเรียงโดยใช้แนวคิดของ heapsort
ที่นี่เราวางองค์ประกอบสูงสุดไว้ที่ส่วนท้าย ทำซ้ำจนกว่าจะจัดเรียงอาร์เรย์
ทีนี้มาดูวิธีแก้ปัญหาในการใช้งานด้านล่างกัน:
ตัวอย่าง
# heapify
def heapify(arr, n, i):
largest = i # largest value
l = 2 * i + 1 # left
r = 2 * i + 2 # right
# if left child exists
if l < n and arr[i] < arr[l]:
largest = l
# if right child exits
if r < n and arr[largest] < arr[r]:
largest = r
# root
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# root.
heapify(arr, n, largest)
# sort
def heapSort(arr):
n = len(arr)
# maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# element extraction
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print (arr[i],end=" ") ผลลัพธ์
Sorted array is 2 3 4 5 5 6 7 8
ตัวแปรทั้งหมดได้รับการประกาศในขอบเขตท้องถิ่นและการอ้างอิงของตัวแปรนั้นดูได้จากรูปด้านบน
บทสรุป
ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างโปรแกรม Python สำหรับ Heap Sort
