У меня вопрос о сортировке кучи. В книге "Алгоритмы" указано, что A.heap-size<= A.length
Я не понимаю разницы между ними. Если массив представляет кучу, то почему существует вероятность того, что A.heap-size меньше A.length. Я знаю, что A.heap-size представляет количество элементов внутри кучи, поэтому почему он не полностью равен числу элементов внутри массива?
В чем разница между размерами A.length и A.heap?
Ответ 1
Инвариант сортировки кучи состоит в том, что первые k элементов массива n-элементов представляют собой кучу на k самых маленьких элементах, а последние n-k-элементы - это самые большие элементы n-k в отсортированном порядке. Последние элементы - вот почему куча не занимает весь массив.
Ответ 2
Просто чтобы расширить ответ. Читайте дальше эту книгу.
A.heap_size массива - это место, где будут размещаться элементы структуры кучи (max_heap или min_heap). Это имеет смысл в области сортировки или очередей. Вы правы: это количество элементов внутри кучи, но оно равно A.length только при первой итерации сортировки кучи.
На следующей итерации после обмена корнем из дерева max_heap (A[1]) с A[i] = A[A.length] (последний элемент внутри массива A) элемент A[1] будет последним элементом значения A и A.heap_sort будет уменьшаться на 1, а max_heap-структура должна быть max_heapified: A[Parent(i)] >= A[i], где Parent(i) возвращает i/2 дерева кучи.
Ответ 3
A.length дает полное no элементов массива, тогда как размер A.heap задает no элементов, которые находятся в отсортированном порядке или нет элементов, которые следуют за состоянием кучи........ А A. length-A.heap или даже не отсортированы даже сейчас и должны быть отсортированы в будущем.
Ответ 4
Из учебника Cormen Algorithm, который я использую:
(это помогло мне)
