题解 | #最小的K个数#

造论子都差点忘记堆排序，一次取头只能取最大或最小，数组本身非排序的

class Solution {
  public:
      //  这里使用堆排序（最小堆）
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      std::vector<int> res;
        //  两个特殊边界
      if (k == 0 || input.empty()) {
        return res;
      }
      
      int size = input.size();
      
      for (int i = 0; i < k; ++i, --size) {
        min_heap_sort(input, size);
        res.push_back(input[0]);
        std::swap(input[0], input[size - 1];
        // input[0] ^= input[size - 1];
        // input[size - 1] ^= input[0];
        // input[0] ^= input[size - 1];
      }
      
      return res;
    }
  private:
    void min_heap_sort(std::vector<int> &input, int size) {
      for (int i = (size >> 1) - 1; i >= 0; --i) {
        sink(input, i, size);
      }
    }
    
    void sink(std::vector<int> &input, int parent, int size) {
      while ((parent << 1) + 1 < size) {
        int child = (parent << 1) + 1;
        
        if (child + 1 < size && input[child] > input[child + 1]) {
          ++child;
        }
        
          //  等于的情况可交换可不交换，为了异或正常，排除等于的情况
        if (input[parent] <= input[child]) {
          break;
        }
        
        // input[parent] ^= input[child];
        // input[child] ^= input[parent];
        // input[parent] ^= input[child];
        
        std::swap(input[parent], input[child]);
        
        parent = child;
      }
    }
};

改进：

class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      std::vector<int> res;
      int size = input.size();
      
      if (input.empty() || k <= 0) {
        return res;
      }
      //  构建堆
      init_heap(input);
      
      for (int i = 0; i < k; ++i) {
        //  堆头元素是最小
        res.push_back(input[0]);
        //  调整堆
        adjust_heap(input, --size);
      }
      
      return res;
    }
  private:
    void sink(std::vector<int> &res, int node, int size) {
      while ((node << 1) + 1 < size) {
        int child = (node << 1) + 1;
        if (child + 1 < size && res[child] > res[child + 1]) {
          ++child;
        }
        if (res[node] <= res[child]) {
          break;
        }
        std::swap(res[node], res[child]);
        node = child;
      }
    }
    void init_heap(std::vector<int> &res) {
      int size = res.size();
      for (int i = (size >> 1) - 1; i >= 0; --i) {
        sink(res, i, size);
      }
    }
    void adjust_heap(std::vector<int> &res, int size) {
      std::swap(res[0], res[size]);
      sink(res, 0, size);
    }
};