Алгоритм поиска и сортировки PHP: сортировка кучи

Алгоритм поиска и сортировки PHP: упражнение 2 с решением

Напишите программу PHP для сортировки списка элементов, используя сортировку кучи.

В информатике, heapsort (изобретенный JWJ Williams в 1964 году) является алгоритмом сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит свои входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, выделяя самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не линейного поиска времени, чтобы найти максимум. Хотя на некоторых машинах он работает несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществом более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort - это алгоритм на месте, но он не является стабильным.

Запуск алгоритма heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой кратко показана древовидная структура кучи для иллюстрации.

Анимационные кредиты: RolandH

Пример решения:

PHP-код:

<?php
  class Node
  {
  private $_i; 
  
  public function __construct($key)
  {
  $this->_i = $key;
  }
  
  public function getKey()
  {
  return $this->_i;
  }
  }
  
  class Heap
  {
  private $heap_Array;
  private $_current_Size;
  
  public function __construct()
  {
  $heap_Array = array();
  $this->_current_Size = 0;
  }
  
  // Remove item with max key 

 public function remove()
  {
  $root = $this->heap_Array[0];
  // put last element into root
  $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];
  $this->bubbleDown(0); 
  return $root; 
  }
  
  // Shift process
  public function bubbleDown($index)
  {
  $larger_Child = null;
  $top = $this->heap_Array[$index]; // save root
  while ($index < (int)($this->_current_Size/2)) { // not on bottom row
  $leftChild = 2 * $index + 1;
  $rightChild = $leftChild + 1;
  
  // find larger child
  if ($rightChild < $this->_current_Size 
  && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) // right child exists?
  {
  $larger_Child = $rightChild;
  } else {
  $larger_Child = $leftChild;
  }
  
  if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {
  break;
  }
  
  // shift child up
  $this->heap_Array[$index] = $this->heap_Array[$larger_Child]; 
  $index = $larger_Child; // go down
  }
  
  $this->heap_Array[$index] = $top; // root to index
  }
  
  public function insertAt($index, Node $newNode)
  {
  $this->heap_Array[$index] = $newNode;
  }
  
  public function incrementSize()
  {
  $this->_current_Size++;
  }
  
  public function getSize()
  {
  return $this->_current_Size;
  }
  
  public function asArray()
  {
  $arr = array();
  for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
  $arr[] = $this->heap_Array[$j]->getKey();
  }
  
  return $arr;
  }
  }
  
  function heapsort(Heap $Heap)
  { 
  $size = $Heap->getSize();
  // "sift" all nodes, except lowest level as it has no children
  for ($j = (int)($size/2) - 1; $j >= 0; $j--) 
  {
  $Heap->bubbleDown($j);
  }
  // sort the heap
  for ($j = $size-1; $j >= 0; $j--) { 
  $BiggestNode = $Heap->remove();
  // use same nodes array for sorted elements
  $Heap->insertAt($j, $BiggestNode);
  }
  
  return $Heap->asArray(); 
  }
  
  $arr = array(3, 0, 2, 5, -1, 4, 1);
  echo "Original Array : ";
  echo implode(', ',$arr ); 
  $Heap = new Heap();
  foreach ($arr as $key => $val) {
  $Node = new Node($val);
  $Heap->insertAt($key, $Node);
  $Heap->incrementSize();
  }
  $result = heapsort($Heap);
  echo "\nSorted Array : ";
  echo implode(', ',$result)."\n";
  ?>
  

Пример вывода:

 Исходный массив: 3, 0, 2, 5, -1, 4, 1                               
Сортированный массив: -1, 0, 1, 2, 3, 4, 5  

Блок-схема:

Редактор кода PHP:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Написать программу PHP для сортировки списка элементов с помощью быстрой сортировки.
Далее: написать программу PHP для сортировки списка элементов с помощью сортировки вставками.