heap演算法視頻

A. 你不得不知道的JVM 垃圾回收

一、四種引用方式
1.1 強引用
1.2 軟引用（SoftReference）
1.3 弱引用（WeakReference）
1.4 虛引用（PhantomReference）

二、如何判斷對象是垃圾
2.1 引用計數法
2.2 根可達性分析

三、垃圾回收演算法
3.1 標記-清除（mark-sweep）
3.2 標記-整理（mark-compact）
3.3 標記-復制（mark-）

四、垃圾收集器
4.1 分類及特點簡述
4.1.1 串列
4.1.2 吞吐量優先
4.1.3 響應時間優先
4.2 串列垃圾回收器詳述
4.2.1 Serial
4.2.2 Serial-Old
4.2.3 流程圖
4.3 吞吐量優先垃圾回收器詳述
4.3.1 JVM相關參數
4.3.2 流程圖
4.4、響應時間優先垃圾回收器詳述
4.4.1 JVM相關參數
4.4.2 流程圖
4.3.3 CMS的特點

五、G1垃圾回收器
5.1 相關JVM參數
5.2 特點
5.3 G1新生代垃圾回收
5.4 G1老年代垃圾回收

只有所有 GC Roots對象都不通過【強引用】引用該對象，該對象才可以被回收。

某個對象只要有一處引用關系，該對象的引用次數就加1，如果一個對象的引用次數為0，則說明該對象是垃圾。

優勢：實現簡單，效率較高

弊端：如果有一對對象之間形成了相互引用，但是這兩個對象都已經沒有被其它對象所引用了，正常情況下，這一對對象應該被作為垃圾回收掉，但是因為形成了相互引用導致無法被回收。

通過GC Root對象開始向下尋找，尋找不到的對象即說明沒有被引用，那麼這些沒有被引用的對象被認定為垃圾。

目前，如下對象可以作為GC Root對象：

很好理解，即在GC的放生時候，先對所有對象進行根可達性分析，藉此標記所有的垃圾對象；所有對象標記完畢之後會進行清理操作。

因此，總體來說，就是先標記再清除。

弊端；標記清除之後會產生大量不連續的內存碎片，碎片太多可能會導致程序運行過程中需要分配較大對象時，無法滿足分配要求導致GC操作。

該回收演算法操作過程基本等同於 標記-清除 演算法只不過，第二步有點區別，該種方式會在清除的過程中進行 整理 操作，這是最大的不同。

優勢：最終不會出現若干空間碎片而導致的空間浪費。

弊端：在整理過程中帶來的計算不可小覷。

該種方式與前兩種有較大的區別：

該種方式會將存儲區分成兩個部分，分別為From、To，其中From區域中可能存在著對象，而To區域始終為空，用做下一次接受數據做准備。

分別有兩個指針指向這兩個區域：From-Pointer、To-Pointer，

優點：這種演算法非常適合早生夕死的對象

缺點：始終有一塊內存區域是未使用的，造成空間的浪費。

特點：

特點：

特點：

JVM開關：-XX:+UseSerialGC = Serial + SerialOld

上圖是：CMS垃圾回收器在老年代GC的工作流程圖：

經過上面的文字分析，新生代的Region個數為所有Region個數的5%；這個數值其實是很小的，那麼當新生代Region不夠用的時候，JVM會劃分更多的Region個數給新生代；

當新生代的Region個數佔比所有Region個數超過 60% 時，就會進行一次新生代的垃圾回收。

新生代垃圾回收會造成STW。

具體的垃圾回收演算法同其它幾個新生代垃圾回收器一樣，新生代都使用復制演算法。

老年代垃圾回收觸發機制與參數-XX:InitaingHeapOccupancyPercent有關。

但是需要注意的是：這一次的老年代回收，其實是一次混合垃圾回收，會同時清理新生代、老年代、Humongous。

與新生代回收演算法一致，依然使用復制演算法，但是垃圾回收的過程等同於老年代響應時間優先的CMS方式

流程分為：

B. c語言（高分）

1.相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數：f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.
2.所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
3.索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位
置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
4.插入法排序
#define N 10
#include"stdio.h"
main()
{ int i,j,k,t,a[N];
clrscr();
printf("Please input %d numbers:\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{if(a[j]>a[i])
{t=a[i];
for(k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
printf("small to big order:\n");
for(i=0;i<N;i++)
printf("%-2d",a[i]);
printf("\n");
getch();
}

C. 堆排序過程

1，實用的排序演算法：選擇排序
（1）選擇排序的基本思想是：每一趟（例如第i趟，i=0，1，2，3，……n-2）在後面n-i個待排序元素中選擇排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟做完，待排序元素只剩下一個，就不用再選了。
（2）三種常用的選擇排序方法
1>直接選擇排序
2>錦標賽排序
3>堆排序
其中，直接排序的思路和實現都比較簡單，並且相比其他排序演算法，直接選擇排序有一個突出的優勢——數據的移動次數少。
（3）直接選擇排序簡介
1>直接選擇排序（select sort）是一種簡單的排序方法，它的基本步驟是：
1）在一組元素V[i]~V[n-1]中選擇具有最小排序碼的元素；
2）若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素對調；
3）在這組元素中剔除這個具有最小排序碼的元素，在剩下的元素V[i+1]~V[n-1]中重復執行1、2步驟，直到剩餘元素只有一個為止。
2>直接選擇排序使用注意
它對一類重要的元素序列具有較好的效率，這就是元素規模很大，而排序碼卻比較小的序列。因為對這種序列進行排序，移動操作所花費的時間要比比較操作的時間大的多，而其他演算法移動操作的次數都要比直接選擇排序來的多，直接選擇排序是一種不穩定的 排序方法。
3>直接選擇排序C++函數代碼

//函數功能，直接選擇排序演算法對數列排序
//函數參數，數列起點，數列終點
void dselect_sort(const int start, const int end) {
for (int i = start; i < end; ++i) {
int min_position = i;
for (int j = i + 1; j <= end; ++j) { //此循環用來尋找最小關鍵碼
if (numbers[j] < numbers[min_position]) {
min_position = j;
}
}
if (min_position != i) { //避免自己與自己交換
swap(numbers[min_position], numbers[i]);

（4）關於錦標賽排序
直接選擇排序中，當n比較大時，排序碼的比較次數相當多，這是因為在後一趟比較選擇時，往往把前一趟已經做過的比較又重復了一遍，沒有把前一趟的比較結果保留下來。
錦標賽排序（tournament sort）克服了這一缺點。它的思想與體育比賽類似，就是把待排序元素兩兩進行競賽，選出其中的勝利者，之後勝利者之間繼續競賽，再選出其中的勝利者，然後重復這一過程，最終構造出勝者樹，從而實現排序的目的。

2，堆排序的排序過程
（1）個人理解：堆排序是選擇排序的一種，所以它也符合選擇排序的整體思想。直接選擇排序是在還未成序的元素中逐個比較選擇，而堆排序是首先建立一個堆（最大堆或最小堆），這使得數列已經「大致」成序，之後只需要局部調整來重建堆即可。建立堆及重建堆這一過程映射到數組中，其實就是一個選擇的過程，只不過不是逐個比較選擇，而是藉助完全二叉樹來做到有目的的比較選擇。這也是堆排序性能優於直接選擇排序的一個體現。
（2）堆排序分為兩個步驟：
1>根據初始輸入數據，利用堆的調整演算法形成初始堆；
2>通過一系列的元素交換和重新調整堆進行排序。
（3）堆排序的排序思路
1>前提，我們是要對n個數據進行遞增排序，也就是說擁有最大排序碼的元素應該在數組的末端。
2>首先建立一個最大堆，則堆的第一個元素heap[0]具有最大的排序碼，將heap[0]與heap[n-1]對調，把具有最大排序碼的元素交換到最後，再對前面n-1個元素，使用堆的調整演算法siftDown(0,n-2)，重新建立最大堆。結果具有次最大排序碼的元素又浮到堆頂，即heap[0]的位置，再對調heap[0]與heap[n-2]，並調用siftDown(0，n-3)，對前n-2個元素重新調整，……如此反復，最後得到一個數列的排序碼遞增序列。
（4）堆排序的排序過程：
下面給出局部調整成最大堆的函數實現siftDown()，這個函數在前面最小堆實現博文中的實現思路已經給出，只需做微小的調整即可用在這里建立最大堆。

D. 堆和棧的區別是啥

堆和棧的區別：
一.堆棧空間分配區別：

1.棧（操作系統）：由操作系統自動分配釋放 ，存放函數的參數值，局部變數的值等。其操作方式類似於數據結構中的棧；

2.堆（操作系統）： 一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由OS回收，分配方式倒是類似於鏈表。

二.堆棧緩存方式區別：

1.棧使用的是一級緩存， 他們通常都是被調用時處於存儲空間中，調用完畢立即釋放；

2.堆是存放在二級緩存中，生命周期由虛擬機的垃圾回收演算法來決定（並不是一旦成為孤兒對象就能被回收）。所以調用這些對象的速度要相對來得低一些。

三.堆棧數據結構區別：

堆（數據結構）：堆可以被看成是一棵樹，如：堆排序；

棧（數據結構）：一種先進後出的數據結構。

(4)heap演算法視頻擴展閱讀：

堆支持以下的基本:

1.build:建立一個空堆；

2.insert:向堆中插入一個新元素；

3.update：將新元素提升使其符合堆的性質；

4.get：獲取當前堆頂元素的值；

5.delete：刪除堆頂元素；

6.heapify：使刪除堆頂元素的堆再次成為堆。

某些堆實現還支持其他的一些操作，如斐波那契堆支持檢查一個堆中是否存在某個元素。

棧的基本演算法

1．進棧（PUSH）演算法

①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；

②置TOP=TOP+1（棧指針加1，指向進棧地址）；

③S(TOP)=X，結束（X為新進棧的元素）；

2．退棧（POP）演算法

①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；

②X=S(TOP)，（退棧後的元素賦給X）：

③TOP=TOP-1，結束（棧指針減1，指向棧頂）。