Как мне улучшить код Python для сортировки кучи?

Question

Я попытался написать программу сортировки кучи самостоятельно для Leetcode 217. Contains Duplicate, как показано ниже, а не используя встроенный метод сортировки Python. Leetcode должен принимать метод сортировки кучи, но по некоторым причинам я не знаю, хотя моя программа сортировки кучи работает хорошо, но я все еще получил отказ от Leetcode. Может ли кто-нибудь помочь?

решаемые ниже код повторно редактироваться с помощью алгоритма Флойда, чтобы инициализировать кучу и передал Leetcode

def heapsort(nums): 

    def swap(i, j): 

     nums[i], nums[j] = nums[j], nums[i] 


    def sift(start, size): 

     l = (start << 1) + 1 # Do not forget() for << 
     r = l + 1 
     largest = start 
     if l <= size - 1 and nums[start] < nums[l]: 
      largest = l 
     if r <= size - 1 and nums[largest] < nums[r]: 
      largest = r 
     if largest != start: 
      swap(start, largest) 
      sift(largest, size) 


    size = len(nums) 

    # Initialize heap (Floyd Algorithm) 
    end = (size >> 1) - 1 
    while end >= 0: 
     sift(end, size) 
     end -= 1 
    swap(0, size - 1) 
    size -= 1 

    # Heapify recursively 
    while size > 1: 
     sift(0, size) 
     swap(0, size - 1) 
     size -= 1 

Answer 1

Ваш код делает слишком много. Вы восстанавливаете всю кучу с каждым элементом, который вы удаляете. Итак, что должен быть алгоритмом O (n log n), является O (n^2).

По сути, ваш код делает это:

while array is not empty 
    rearrange array into a heap 
    extract the smallest item 

Перегруппировка кучу дублей, в лучшем случае, O (N) времени. И извлечение наименьшего числа принимает O (log n). Таким образом, ваш алгоритм O (n^2 + n log n).

На самом деле, ваш метод построения кучи снизу вверх - это O (n log n). Таким образом, ваш алгоритм сортировки кучи на самом деле равен O ((n + 1) * (n log n)). В любом случае это очень субоптимальный алгоритм.

Идея создания кучи заключается в том, что вы упорядочиваете массив в кучу один раз. Это операция O (n). Алгоритм довольно прост:

for i = heap.length/2 downto 1 
    siftDown(i) 

Это называется Floyd's algorithm, после того, как его изобретателя.

Обратите внимание, что мы начинаем посередине массива и просеиваем down. Идея состоит в том, что последние n/2 элементы являются листовыми узлами, поэтому в любом случае они не могут просеиваться. Начав с n/2 и работая назад, мы можем наследовать весь массив в O (n) времени.

После того, как массив устроен в кучу, мы делаем следующее:

while heap is not empty 
    output the item at heap[0] 
    move the item at the end of the heap to heap[0] 
    reduce the count of items by 1 
    siftDown(0) 

Элемент в куче [0] является наименьшим элемент, оставшийся в куче, поэтому мы выводим ее. Тогда нет необходимости перестраивать всю кучу. Все, что вам нужно сделать, это взять последний предмет в кучу, поместить его вверху и просеять его на место. Остальная куча остается в силе.

Выполнение этих изменений должно сократить время работы, хотя я не знаю, сделает ли это ваш код приемлемым. Существует еще один способ проверить дубликаты. Для этого требуется O (n) дополнительное пространство, но это быстрее, чем сортировка.

Идея состоит в том, чтобы создать хеш-таблицу, а затем пройти через массив, проверяя, находится ли элемент в хэш-таблице. Если нет, добавьте его. Если это уже в таблице, то это дубликат.Как отметил Гарольд, у Python есть тип set, который делает такую ​​вещь легкой в ​​использовании.

Answer 2

Говоря о кучного рода, рассмотрим heapq питона модуль. Он существует именно для этой цели - обеспечивает реализацию алгоритма очереди кучи. Он не разработан не очень удобно, но есть удобные wrappers - вы можете сами это сделать.

Говоря о поиске дубликатов, любой алгоритм сортировки n log(n) не должен быть достаточно эффективным. Взгляните на python set встроенный!