Слияние кода завершено, страница обновится автоматически
首先将数组映射为一棵完全二叉树
规则：对于 i 下标位置的元素，它的左孩子下标为 2*i+1，右孩子下标为 2*(i+1).
维护一个以root下标为根，末尾下标为len的大根堆
如果root的两个孩子有比它大的，则将root和那个最大元素交换位置，并对那个子树进行递归维护.
(define (MaxHeapify heap root len)
(define (Left i) (+ (* i 2) 1))
(define (Right i) (* (+ i 1) 2))
(let ((left (Left root))
(right (Right root))
(largest root))
(begin
(if (and (<= left len)
(> (vector-ref heap left)
(vector-ref heap root)))
(set! largest left))
(if (and (<= right len)
(> (vector-ref heap right)
(vector-ref heap largest)))
(set! largest right))
(if (not (= largest root))
(let ((head (vector-ref heap root)))
(begin
(vector-set! heap root (vector-ref heap largest))
(vector-set! heap largest head)
(MaxHeapify heap largest len)))))))
初始化大根堆
从堆中的最后一个有孩子的节点开始从右向左、从下向上，以每个节点为根维护一个大根堆.
(define (BuildMaxHeap heap)
(define (build-iter i)
(if (>= i 0)
(begin
(MaxHeapify heap i (- (vector-length heap) 1))
(build-iter (- i 1)))))
(build-iter (- (div (vector-length heap) 2) 1)))
堆排序
从初始的大根堆开始，每次将0下标位置和len下标位置的元素交换，并len := len-1，然后继续对0到len位置的元素进行堆排序，直到len = 0.
(define (HeapSort heap)
(define (sort-iter i)
(if (>= i 1)
(let ((max (vector-ref heap 0)))
(begin
(vector-set! heap 0 (vector-ref heap i))
(vector-set! heap i max)
(MaxHeapify heap 0 (- i 1))
(sort-iter (- i 1))))))
(BuildMaxHeap heap)
(sort-iter (- (vector-length heap) 1))
heap)
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )