堆、堆排序與索引堆
2022-04-19 11:18:59

#include <iostream>
#include <algorithm>
#include <cassert>

template <typename Item>
class MaxHeap {
  private:
    Item* data;
    //堆的實(shí)際容量（不包括data[0]）
    int capacity;
    //堆目前的元素?cái)?shù)量
    int count;

    void shiftUp(int index) {
      while (index > 1) {
        if (data[index] > data[index / 2])
          std::swap(data[index],data[index / 2]);
        index /= 2;
      }
    }

    void shiftDown(int index) {
      while (index * 2 <= count) {
        int j =2 * index;
        if (j + 1 <= count && data[j] < data[j + 1]) {
          j++;
        }

        if (data[j] <= data[index]) {
          break;
        }

        std::swap(data[j],data[index]);
        index = j;
      }
    }

  public:
    MaxHeap(int capacity) {
      this -> capacity = capacity;
      data = new Item[capacity + 1];
      count = 0;
    }

    ~MaxHeap() {
      delete [] data;
    }

    //插入元素
    void insert(Item item) {
      assert(count < capacity);
      data[++count] = item;
      //將item浮動(dòng)到合適的位置
      shiftUp(count);
    }

    //彈出根元素
    Item pop() {
      assert(count > 0);
      Item root = data[1];
      data[1] = data[count];
      count--;
      shiftDown(1);
      return root;
    }

    void print() {
      for (int i = 1; i <= count; i++) {
        std::cout << data[i] << " ";
      }
    }

    //獲取堆的當(dāng)前大小
    int size() {
      return count;
    }
    //判斷堆是否為空
    bool isEmpty() {
      return count == 0;
    }
};

template <typename T>
template heapSort1(T arr[],int n){
  MaxHeap<T> maxHeap = MaxHeap<T>(n);
  for (int i = 0;i < n;i++){
    maxHeap.insert(arr[i]);
  }
  for (int i = n - 1;i >= 0;i--){
    arr[i] = maxHeap.pop();
  }
}

//利用數(shù)組進(jìn)行堆的初始化
MaxHeap(Item arr[],int n) {
  data = new Item[n + 1];
  this -> capacity = n;
  this -> count = n;

  for (int i = 0; i < n; i ++) {
    data[i + 1] = arr[i];
  }

  //從第一個(gè)不是葉子節(jié)點(diǎn)的節(jié)點(diǎn)開(kāi)始向上，逐次使用shiftDown方法
  for (int i = count / 2; i > 0 ; i --) {
    shiftDown(i);
  }
}

template <typename T>

template heapSort2(T arr[],int n){
  MaxHeap<T> maxHeap = MaxHeap<T>(arr,n);
  for (int i = n - 1;i >= 0;i--){
    arr[i] = maxHeap.pop();
  }
}

//堆排序算法--最終版 
//在原數(shù)組中進(jìn)行堆排序，不占用額外空間
//首先對(duì)原數(shù)組進(jìn)行heapify
//然后將arr[0]和最后一個(gè)元素進(jìn)行交換，重新對(duì)第一個(gè)元素進(jìn)行heapify，以此類推

//注意：索引從0開(kāi)始
//左子樹(shù)：2 * i + 1
//右子樹(shù)：2 * i + 2
//父節(jié)點(diǎn)：(i - 1) / 2

#include <iostream>
#include <cassert>

template <typename T>
void __shiftDown(T arr[],int n,int index) {
  while (2 * index + 1 < n) {
    int j = 2 * index + 1;
    if (j + 1 < n && arr[j] < arr[j + 1])
      j++;
    if (arr[index] > arr[j]) {
      break;
    }
    std::swap(arr[index],arr[j]);
    index = j;
  }
}

template <typename T>
void heapSort(T arr[] ,int n) {
  //從第一個(gè)不是葉子節(jié)點(diǎn)的元素開(kāi)始向上，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行shiftDown
  for (int i = (n - 1) / 2; i >= 0; i--) {
    __shiftDown(arr, n, i);
  }

  for (int i = n - 1; i > 0 ; i --) {
    std::swap(arr[i], arr[0]);
    __shiftDown(arr, i, 0);
  }
}

#include <iostream>
#include <algorithm>
#include <cassert>

template <typename Item>
class IndexMaxHeap{
  private:
    //存儲(chǔ)元素的數(shù)組
    Item* data;
    //存儲(chǔ)元素索引的數(shù)組
    int* indexes;
    //當(dāng)前堆中元素個(gè)數(shù)
    int count;
    //堆容量
    int capacity;
    void shiftUp(int i){
      while(i > 1){
        if (data[indexes[i]] > data[indexes[i / 2]]){
          std::swap(indexes[i],indexes[i / 2]);
        }
        i /= 2;
      }
    }

    void shiftDown(int i){
      int j = 0;
      while (2 * i <= count){
        j = 2 * i;

        if (j + 1 <= count && data[indexes[j]] < data[indexes[j + 1]])
          j += 1;

        if (data[indexes[i]] >= data[indexes[j]])
          break;

        std::swap(indexes[i],indexes[j]);
        i = j;
      }
    }

  public:
    IndexMaxHeap(int capacity){
      data = new Item[capacity + 1];
      indexes = new int[capacity + 1];
      this -> capacity = capacity;
      this -> count = 0;
    }
    ~IndexMaxHeap(){
      delete [] data;
      delete [] indexes;
    }

    int size(){
      return count;
    }
    //注意，對(duì)用戶而言，i是從0開(kāi)始的，但我們存儲(chǔ)是從1開(kāi)始，編程實(shí)需要注意
    void insert(int i,Item item){
      assert(count < capcacity);
      assert(i > 0 && i + 1 < capcacity);

      data[++i] = item;
      indexes[++count] = i;
      shiftUp(count);
    }

    Item pop(){
      assert(count > 0);
      Item root = data[indexes[1]];
      indexes[1]=indexes[count];
      count--;
      shiftDown(1);
      return root;
    }

    //返回最大元素的索引
    int popMaxIndex(){
      assert(count > 0);
      //注意，對(duì)用戶來(lái)說(shuō)從0開(kāi)始
      int root = indexes[1] - 1;
      indexes[1] = indexes[count];
      std::swap(indexes[1],indexes[count]);
      count--;
      shiftDown(1);
      return root;
    }

    Item getItem(int i){
      return data[i + 1];
    }
    //修改索引為i的item
    //O(n)
    void change(int i,Item newItem){
      data[++i] = newItem;
      //接下來(lái)我們需要找到newItem(即data[i]在indexes中的位置)
      //indexes[j] = i,j表示的就是data[i]在堆中的位置
      //將i嘗試shiftUp操作或者shiftDown
      for (int j = 1;j < count; j++){
        if (indexes[j] == i ){
          shiftUp(j);
          shiftDown(j);
        }
      }

    }
}

index[i] = j;
reverse[j] = i;

bool isContains(int i){
  assert(i + 1 >=1 && i + 1 <=capacity);
  return reverse[i + 1] != 0;
}