大根堆與小根堆的理解，如何手寫一個堆，以及什么時候用自己手寫的堆，什么時候用語言提供堆的api，（二者的區別）

定義

Heap是一種資料結構具有以下的特點：
1）完全二叉樹；
2）heap中存盤的值是偏序；

Min-heap: 父節點的值小于或等于子節點的值；
Max-heap: 父節點的值大于或等于子節點的值；
用通俗語言來說，大根堆就是每個最大的數字在每個子樹的最上方，及大根堆pop值為最大值，小根堆反之

堆的存盤

堆的存盤一般由陣串列示，由于堆的實質就是完全二叉樹，所以對于每個i來說（從0開始）,左右孩子分別為2i+1,2i+2，父節點為（i-1）/2，

堆的核心操作（手寫與系統均有）

heapinsert與heapify
1.heapinsert:加入一個節點，通過上升的方式，依次進行比較，（上升操作），時間復雜度為o（logN）因為樹的深度為logN

swap為交換操作

private void heapInsert(int[] arr, int index) {
			while (arr[index] > arr[(index - 1) / 2]) {
				swap(arr, index, (index - 1) / 2);
				index = (index - 1) / 2;
			}
		}

2.heapify：彈出根結點之后的，將剩余變成堆的操作（下沉操作），因為彈出根結點后，會將陣列最后面的數字頂替為根結點，所以只需將該結點進行下沉操作即可，時間復雜度為o（logN）樹的深度為logN

swap為交換操作

/**
		 * 
		 * @param arr 陣列
		 * @param index 索引
		 * @param heapSize 堆大小
		 */
		private void heapify(int[] arr, int index, int heapSize) {
			int left = index * 2 + 1;
			while (left < heapSize) {
				int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
				largest = arr[largest] > arr[index] ? largest : index;
				if (largest == index) {
					break;
				}
				swap(arr, largest, index);
				index = largest;
				left = index * 2 + 1;
			}
		}

堆排序

首先堆排序分為2部分
1.將一個無序陣列變成堆
2.將堆進行排序核心操作（heapfiy，因為如果是大根堆的話，最大值在上方一直，heapfiy即可＋swap（交換）即可）

首先分析第一個部分
通常有2中方法
1.最常用的一種是將陣列依次遍歷，最后一次加入堆中，便可將陣列變成堆，但是此種方法的因為將陣列中所以數進行遍歷 （N），將每個數進行heapinsert（logN），所以時間復雜度為O（N*logN）

// O(N*logN)
		for (int i = 0; i < arr.length; i++) { // O(N)
			heapInsert(arr, i); // O(logN)
		}

2.對此有一種優化方法，從陣列尾部開始遍歷，然后進行下沉，由于是從尾部，那邊可以得到下沉數字一定為有限常數

可以嘗試這么理解，剛開始從尾部遍歷，那么底部只有一層嘛，這時候heapify就為下沉0，倒數第二層時候，heapify為下沉1層，倒數第三層，heapify為下沉2層，有限個數時間復雜度為o(1)
那么總體便為o(N*1)=O(N)

for (int i = arr.length - 1; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}

然后分析第二個部分
變成堆之后，例如大根堆，最大是數字是根結點，那么將最大的數字為尾部交換，然后將–heapsize,然后回圈依次swap，heapify就ok了
這個方法的時間復雜度為o（n*logN）從頂部開始下沉，heapify是logN哈

詳細代碼如下

// 堆排序額外空間復雜度O(1)
	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// O(N*logN)
//		for (int i = 0; i < arr.length; i++) { // O(N)
//			heapInsert(arr, i); // O(logN)
//		}
		//O(N)
		for (int i = arr.length - 1; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
		int heapSize = arr.length;
		swap(arr, 0, --heapSize);
		// O(N*logN)
		while (heapSize > 0) { // O(N)
			heapify(arr, 0, heapSize); // O(logN)
			swap(arr, 0, --heapSize); // O(1)
		}
	}

什么時候使用語言自帶api，什么時候使用自己的手寫api

首先我們需要明確一點，我們需要重寫撰寫一個類代替原有api，肯定當前api無法滿足我們的情況，我們來重寫api達到我們的效果

我們現在來看一種效果，我們現在不是int型別，是一個參考型別例如Teacher（假設包含id，name），我們通過比較器（后續博客會有一篇詳細結束比較器的，會更新的，嘿嘿）
對其進行id比較，變成堆之后，（切記是以及變成堆之后）我們對其中某一個Teacher進行操作，將他的id變化，那么這個時候整個堆會發生巨大變化（變成不是堆結構），而這不是用戶本意，用戶只是想修改某一個teacher的資訊，然后依然希望這個list是堆，換句話說，修改之后依然希望類自己進行維護，修改之后的結構自己進行復原變成堆

所以這個時候，語言自帶的api無法完成這個操作（java，python沒有，就算某些語言有，也是進行整體heapinsert，時間復雜度太高不適應）這個時候我們便需要自己首先一個api，來完成此操作

手寫解決上述問題優化的堆

核心思想便是使用HashMap<T, Integer> indexMap;對修改位置的索引進行記錄，在push的時候將指標（地址）與索引進行記錄在pop的時候進行洗掉，

核心在于regsion
通過值可以得到索引，然后對索引依次進行heapify與heapinsert巧妙在于因為堆的特性要么上升要么下沉,時間復雜度與o（logN）

public static class MyHeap<T> {
		private ArrayList<T> heap;
		private HashMap<T, Integer> indexMap;
		private int heapSize;
		private Comparator<? super T> comparator;

		public MyHeap(Comparator<? super T> com) {
			heap = new ArrayList<>();
			indexMap = new HashMap<>();
			heapSize = 0;
			comparator = com;
		}
		public boolean isEmpty() {
			return heapSize == 0;
		}
		public int size() {
			return heapSize;
		}
		public boolean contains(T key) {
			return indexMap.containsKey(key);
		}

		public void push(T value) {
			heap.add(value);
			indexMap.put(value, heapSize);
			heapInsert(heapSize++);
		}

		public T pop() {
			T ans = heap.get(0);
			int end = heapSize - 1;
			swap(0, end);
			heap.remove(end);
			indexMap.remove(ans);
			heapify(0, --heapSize);
			return ans;
		}
		public void resign(T value) {
			int valueIndex = indexMap.get(value);
			heapInsert(valueIndex);
			heapify(valueIndex, heapSize);
		}
		private void heapInsert(int index) {
			while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
				swap(index, (index - 1) / 2);
				index = (index - 1) / 2;
			}
		}
		private void heapify(int index, int heapSize) {
			int left = index * 2 + 1;
			while (left < heapSize) {
				int largest = left + 1 < heapSize && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0)
						? left + 1
						: left;
				largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
				if (largest == index) {
					break;
				}
				swap(largest, index);
				index = largest;
				left = index * 2 + 1;
			}
		}
		private void swap(int i, int j) {
			T o1 = heap.get(i);
			T o2 = heap.get(j);
			heap.set(i, o2);
			heap.set(j, o1);
			indexMap.put(o1, j);
			indexMap.put(o2, i);
		}
	}

結語

第一次寫博客，搞了一晚上，肯定寫的不好，希望大家不吝賜教，也希望能幫助到大家，也為自己總結使用，如果有不對的地方，歡迎大家指正