/*
- @Author: sumBorn
- @Date: 2022-03-01 21:45:51
- @Description:
空間復(fù)雜度O(NlogN)
時(shí)間復(fù)雜度O(1)
不穩(wěn)定排序
堆的基本思想：
- 和樹的區(qū)別 http://m.itdecent.cn/p/6b526aa481b1
- shiftUp()：對(duì)于最大堆來說，如果某個(gè)節(jié)點(diǎn)比自己父節(jié)點(diǎn)大，就要往上移，和父節(jié)點(diǎn)交換位置
- shiftDown()<堆化>：對(duì)于最大堆來說，如果某個(gè)節(jié)點(diǎn)比自己父節(jié)點(diǎn)小，就要往下移，和子節(jié)點(diǎn)交換位置、
- 兩者都是一個(gè)遞歸的過程，所以時(shí)間復(fù)雜度是O(logN)
基本步驟：
- 對(duì)序列進(jìn)行原地建堆
- 重復(fù)以下流程,直到元素個(gè)數(shù)為1
- 交換堆頂元素與堆尾元素
- 堆的元素?cái)?shù)量減1
- 堆0位置的元素進(jìn)行siftdown操作
例子：
0:{50,21,80,43,38,14}
1:{80,43,50,21,38,14}
2:{50,43,14,21,38,80}
3:{43,38,14,21,50,80}
4:{38,21,14,43,50,80}
...
*/
/**
@description: 遞歸實(shí)現(xiàn) 看著更棒
@param {*}
-
@return {*}
*/
public class Solution
{
public void HeapSort(int[] arr)
{
int endIndex = arr.Length - 1;
int beginIndex = (endIndex - 1) / 2;//shiftdown第一次判斷有子節(jié)點(diǎn)的那個(gè)父節(jié)點(diǎn)，所有的葉子節(jié)點(diǎn)都沒有子節(jié)點(diǎn)根本不需要進(jìn)行操作，只有有子節(jié)點(diǎn)的節(jié)點(diǎn)才需要進(jìn)行操作，所以找到第一個(gè)有葉子節(jié)點(diǎn)的節(jié)點(diǎn)
for (int i = beginIndex; i >= 0; i--)
{
this.Shiftdown(i, arr, endIndex); //需要shiftdown的索引元素，整個(gè)數(shù)組，這個(gè)元素可以down到最低的位置，也就是數(shù)組的最末尾
}for (int i = endIndex; i >= 0; i--) { this.Swap(i, 0, arr); this.Shiftdown(0, arr, i - 1);//交換完 down可以的最低位置少了一位 }}
public void Shiftdown(int index, int[] arr, int limitIndex)
{
int leftIndex = index * 2 + 1;
int rightIndex = leftIndex + 1;
int maxIndex = leftIndex;//先默認(rèn)左節(jié)點(diǎn)比右節(jié)點(diǎn)大if (leftIndex > limitIndex) return; if (leftIndex < limitIndex && arr[leftIndex] < arr[rightIndex]) maxIndex = rightIndex; if (arr[maxIndex] > arr[index]) { this.Swap(maxIndex, index, arr); this.Shiftdown(maxIndex, arr, limitIndex); }}
public void Swap(int i, int j, int[] arr)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
/**
@description: 正常實(shí)現(xiàn)
@param {*}
-
@return {*}
*/
public class Solution
{
public void HeapSort(int[] arr)
{
for (int i = arr.Length / 2 - 1; i >= 0; i--)
{
this.Shiftdown(i, arr, arr.Length - 1);
}for (int i = arr.Length - 1; i >= 0; i--) { this.Swap(i, 0, arr); this.Shiftdown(0, arr, i - 1);// 從根節(jié)點(diǎn)向下調(diào)整，每次取出一個(gè)數(shù)值，集合長(zhǎng)度逐漸減小 }}
public void Swap(int i, int j, int[] arr)
{
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}public void Shiftdown(int index, int[] arr, int limitIndex)
{
int node = arr[index];
while (index <= limitIndex)
{
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
if (leftIndex > limitIndex)
{
//左右節(jié)點(diǎn)都沒有
break;
}
else if (rightIndex > limitIndex)
{
//左節(jié)點(diǎn)在，右節(jié)點(diǎn)沒了
int left = arr[leftIndex];
if (left > node)
{
arr[index] = left;
index = leftIndex;
}
else
{
break;
}
}
else
{
//左右節(jié)點(diǎn)都在
int left = arr[leftIndex];
int right = arr[rightIndex];
int maxIndex = left >= right ? leftIndex : rightIndex;
int max = arr[maxIndex];
if (max < node)
{
break;
}
else
{
//和較大值交換
arr[index] = max;
index = maxIndex;
}
}
}
arr[index] = node;
}public void ShiftUp(int index, int[] arr)
{
int node = arr[index];
while (index > 0)
{
int parentIndex = (int)((index - 1) / 2);
int parent = arr[parentIndex];if (parent > node) break; arr[index] = parent; index = parentIndex; } arr[index] = node;}
}
