【算法导论】第六章 堆 学习笔记

 建堆 BUILD_MAX_HEAP
    2. 堆维护 MAX_HEAPITY
    3. 断尾重构 HEAPSORT
    
      
      
      
    
    AI写代码

    MAX_HEAPITY(A,i):
    left=i*2+1;
    right=i*2+2;
    //假设以left和right均为最大堆
    //判断left和right的合理性 < heap_size
    //比较节点与left、right的大小，
    //将大的节点与i交换，并递归调用MAX_HEAPITY(A,max_index)
    
      
      
      
      
      
      
      
    
    AI写代码

    BUILD_MAX_HEAP(A):
    for i=(n+1)/2-1 to 0:
        MAX_HEAPITY(A,i)
    
      
      
      
    
    AI写代码

    HEAPSORT(A):
    for i=A.length to 1:
        exchange A[0],A[i]
        --A.heap_size;
        MAX_HEAPIFY(A,0);//对新的堆顶进行排序维护
    
      
      
      
      
      
    
    AI写代码

    //MaxHeap.h
    #ifndef LINTCODE_MAXHEAP_H
    #define LINTCODE_MAXHEAP_H
    
    #include <vector>
    
    using namespace std;
    
    //原地排序算法
    class MaxHeap {
    private:
    void exchangeNum(vector<int> &A, int i, int j);
    
    void maxHeapity(vector<int> &A, int index, int &heap_size);
    
    void buildMaxHeap(vector<int>& A, int &heap_size);
    
    public:
    void heapSort(vector<int>& A);
    };
    
    
    #endif //LINTCODE_MAXHEAP_H
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    AI写代码

    //MaxHeap.cpp
    
    #include "MaxHeap.h"
    using namespace std;
    
    void MaxHeap::exchangeNum(vector<int> &A, int i, int j) {
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
    
    //数组下标从0开始
    void MaxHeap::maxHeapity(vector<int> &A, int index, int &heap_size) {
      int left = index * 2 + 1;
      int right = index * 2 + 2;
      int i = index;
      i = (left < heap_size && A[left] > A[i]) ? left : i;
      i = (right < heap_size && A[right] > A[i]) ? right : i;
    
      if (i != index) {
    exchangeNum(A, i, index);
    //递归调用
    maxHeapity(A, i, heap_size);
      }
    
    }
    
    void MaxHeap::buildMaxHeap(vector<int> &A, int &heap_size) {
      int n = A.size();
      int leaf_num = (n + 1) / 2; //节点数为n的堆，的叶子节点号为(n+1)/2，(n+1)/2+1,...,n
      for (int i = leaf_num - 1; i >= 0; --i) {
    maxHeapity(A, i, heap_size);
      }
    }
    
    //断尾法，得排序数组
    void MaxHeap::heapSort(vector<int> &A) {
      int heap_size = A.size();
      buildMaxHeap(A, heap_size);
    
      for (int i = A.size() - 1; i > 0; --i) {
    exchangeNum(A, 0, i); //交换尾部和当前堆顶元素
    --heap_size;
    maxHeapity(A, 0, heap_size);
      }
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    AI写代码