Question

На основе алгоритма пирамидальной сортировки составить программу, которая проводит сортировку массива целых чисел.

Answer 1

язык программирования python

def heapify(nums, heap_size, root_index):  

   largest = root_index

   left_child = (2 * root_index) + 1

   right_child = (2 * root_index) + 2

   if left_child < heap_size and nums[left_child] > nums[largest]:

       largest = left_child

   if right_child < heap_size and nums[right_child] > nums[largest]:

       largest = right_child

   if largest != root_index:

       nums[root_index], nums[largest] = nums[largest], nums[root_index]

       heapify(nums, heap_size, largest)

def heap_sort(nums):  

   n = len(nums)

   for i in range(n, -1, -1):

       heapify(nums, n, i)

   for i in range(n - 1, 0, -1):

       nums[i], nums[0] = nums[0], nums[i]

       heapify(nums, i, 0)

list_of_nums = [int(item) for item in input('Введите элементы через пробел: ').split()]  

heap_sort(list_of_nums)  

print(list_of_nums)  

Answer 2

Конечно, вот пример программы на Python, реализующей алгоритм пирамидальной сортировки для сортировки массива целых чисел:

pythonCopy code
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
        
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
        
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# Пример использования
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Отсортированный массив:")
print(arr)

Вы можете заменить массив arr на свой собственный массив чисел для тестирования. Программа создает максимальную пирамиду (max heap) из массива, а затем выполняет сортировку путем поочередной замены корня пирамиды с последним элементом и перестройкой пирамиды.