一、二叉樹
1.1 二叉樹遍歷
中序遍歷块请、前序遍歷脐供、后序遍歷(根據根節(jié)點遍歷次序劃分)
中序遍歷：
//遞歸:
var inorderTraversal = function (root, array = []) {
if (root) {
inorderTraversal(root.left, array);
array.push(root.val);
inorderTraversal(root.right, array);
}
return array;
};
//非遞歸
var inorderTraversal = function (root) {
const result = [];
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
};
1.2 重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結果拓颓，請重建出該二叉樹井辆。
function reConstructBinaryTree(pre, vin) {
// write code here
if (pre.length === 0 || vin.length === 0) {
return null;
}
// 前序第一個是根節(jié)點，也是中序左右子樹的分割點
const index = vin.indexOf(pre[0]),
left = vin.slice(0, index),
right = vin.slice(index + 1);
return {
val: pre[0],
// 遞歸左右子樹的前序溶握、中序
left: reConstructBinaryTree(pre.slice(1, index + 1), left),
right: reConstructBinaryTree(pre.slice(index + 1), right)
};
}
1.3 二叉樹的深度
//最大深度
function TreeDepth(pRoot) {
return !pRoot ? 0 : Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1
}
//最小深度
var minDepth = function (root) {
if (!root) {
return 0;
}
if (!root.left) {
return 1 + minDepth(root.right);
}
if (!root.right) {
return 1 + minDepth(root.left);
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};
1.4 平衡二叉樹
判斷是否為平衡二叉樹
function IsBalanced_Solution(pRoot) {
return balanced(pRoot) != -1;
}
function balanced(node) {
if (!node) {
return 0;
}
const left = balanced(node.left);
const right = balanced(node.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
1.5 二叉搜索樹
正常情況下二叉搜索樹時間復雜度為O(log2n), 極端情況下為O(n)故需要AVL樹杯缺。
二叉搜索樹的第k小的節(jié)點，即考察中序遍歷睡榆。
//遞歸實現
function KthNode(pRoot, k) {
const arr = [];
loopThrough(pRoot, arr);
if (k > 0 && k <= arr.length) {
return arr[k - 1];
}
return null;
}
function loopThrough(node, arr) {
if (node) {
loopThrough(node.left, arr);
arr.push(node);
loopThrough(node.right, arr);
}
}
1.6 AVL樹
AVL樹萍肆，也稱平衡二叉搜索樹，AVL是其發(fā)明者姓名簡寫胀屿。AVL樹屬于樹的一種塘揣，而且它也是一棵二叉搜索樹，不同的是他通過一定機制能保證二叉搜索樹的平衡宿崭，平衡的二叉搜索樹的查詢效率更高亲铡。
特點
- AVL樹是一棵二叉搜索樹。
- AVL樹的左右子節(jié)點也是AVL樹。
- AVL樹擁有二叉搜索樹的所有基本特點奖蔓。
- 每個節(jié)點的左右子節(jié)點的高度之差的絕對值最多為1赞草，即平衡因子為范圍為[-1, 1]。
image.png
旋轉
image.png
image.png
相關代碼
/**
* AVL樹節(jié)點的構造函數
* @constructor
*/
function AVLTreeNode(key) {
this.key = key;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
/**
* AVL樹的構造函數吆鹤。如果沒有傳有效的keyName厨疙，使用data進行比較；否則使用data[keyName]進行比較
*
* @param {string} [keyName] - 可選參數疑务。關鍵碼在data中的字段名
* @constructor
*/
function AVLTree(keyName) {
this.root = null;
//這是我們計算當前節(jié)點的高度的方法,遞歸計算
let getHeight = function (node) {
// 如果沒有那就為0
if(node === null) {
return 0;
} else {
return Math.max(getHeight(node.leftChild),getHeight(node.rightChild)) + 1;
}
};
//向左的單旋轉
let rotateLL = function (node) {
let tmp = node.rightChild;
node.rightChild = tmp.leftChild;
tmp.leftChild = node;
return tmp;
};
//向右的單旋轉
let rotateRR = function (node) {
let tmp = node.leftChild;
node.leftChild = tmp.rightChild;
tmp.rightChild = node;
return tmp;
};
//先左后右雙旋轉
let rotateLR = function (node) {
node.leftChild = rotateLL(node.leftChild);
return rotateRR(node);
};
//先右后左雙旋轉
let rotateRL = function (node) {
node.rightChild = rotateRR(node.rightChild);
return rotateLL(node);
};
//方法保證 整顆樹平衡
function checkIsBalance(node) {
if (node == null) {
return node;
}
// 左子樹高度比右子樹高度大 父節(jié)點平衡因子為-2
if (getHeight(node.leftChild) - getHeight(node.rightChild) > 1) {
if (getHeight(node.leftChild.leftChild) >= getHeight(node.leftChild.rightChild)) {
// 如果左子樹的左子樹高度大于等于左子樹的右子樹高度 左子節(jié)點為-1和0
// 直接進行右單旋
node = rotateRR(node);
} else {
//如果左子節(jié)點為1沾凄，需要先左后右雙旋
node = rotateLR(node);
}
// 右子樹高度比左子樹高度大1以上 父節(jié)點平衡因子為2
} else if (getHeight(node.rightChild) - getHeight(node.leftChild) > 1) {
if (getHeight(node.rightChild.rightChild) >= getHeight(node.rightChild.leftChild)) {
// 如果右子樹的右子樹高度大于等于右子樹的左子樹高度
// 直接進行左單旋
node = rotateLL(node);
} else {
// 否則需要右左雙旋
node = rotateRL(node);
}
}
return node;
}
//插入方法：
let insertNode = function(node, newNode){
if (node == null){
node = newNode;
return node;
} else if (newNode.key < node.key){
// 在左子樹里插入 同搜索二叉樹一致
if (node.leftChild === null){
node.leftChild = newNode;
return node;
} else {
node.leftChild = insertNode(node.leftChild, newNode);
//更新整棵樹
node = checkIsBalance(node);
}
} else if (newNode.key > node.key){
//右子樹里插入
if (node.rightChild === null){
node.rightChild = newNode;
return node;
} else {
node.rightChild = insertNode(node.rightChild, newNode);
node = checkIsBalance(node);
}
}
return node;
};
this.insert = function (data) {
let newNode = new AVLTreeNode(data);
this.root = insertNode(this.root, newNode);
};
this.delete = function (data) {
this.root = deleteData(this.root, data);
};
//刪除制定節(jié)點
function deleteData(node, data) {
if( node === null){
return null;
}
//如果小于就在左子樹中刪除
if(data < node.key){
node.leftChild = deleteData(node.leftChild, data);
node = checkIsBalance(node);
return node
}else if(data > node.key){
node.rightChild = deleteData(node.rightChild, data);
node = checkIsBalance(node);
return node
}else{
//刪除的data等于node.key
//如果此節(jié)點有兩個子節(jié)點
if(!!node.leftChild && !!node.rightChild){
let tempNode = node.rightChild;
while ( null !== tempNode.leftChild){
//找到右子樹中最小的節(jié)點
tempNode = tempNode.leftChild;
}
//右子樹中最小的節(jié)點賦值給當前節(jié)點
node.key = tempNode.key ;
//刪除右子樹中最小值的節(jié)點
node.rightChild = deleteData(node.rightChild, tempNode.key);
node = checkIsBalance(node);
return node;
}else {
//只有一個或者是葉節(jié)點
//葉節(jié)點
if( null === node.leftChild && null === node.rightChild){
node = null;
return node;
}
//只有右
if( null === node.leftChild){
node = node.rightChild;
return node;
}else if( null === node.rightChild){
//只有左
node = node.leftChild;
return node;
}
}
}
}
this.print = function () {
console.log(this.root);
debugger
}
}
/**
*打印
*/
const avl = new AVLTree();
const existData = [];
for (let len = 10; len > 0; len--) {
const data = ~~(100 * Math.random());
if (-1 === existData.indexOf(data)) {
existData.push(data);
avl.insert(data);
} else {
len++;
}
}
existData.forEach(item => avl.insert(item));
console.log('existData:', existData.map(item => item));
avl.print();
const deletedData = [];
for (let len = 3; len > 0; len--) {
const index = ~~(Math.random() * existData.length);
deletedData.push(existData[index]);
avl.delete(existData.splice(index, 1));
}
console.log('deletedData: ', deletedData.map(item => item));
avl.print();
/*
————————————————
版權聲明：本文為CSDN博主「Funfction_Zero」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權協(xié)議知允，轉載請附上原文出處鏈接及本聲明撒蟀。
原文鏈接：https://blog.csdn.net/wf00334814/java/article/details/84103036
*/
總結
- 二叉搜索樹的不穩(wěn)定性，就有可能退化為近似鏈或鏈廊镜，查詢時間復雜度就退化為 O(n)牙肝。當 n 很大的時候，性能就大大降低嗤朴，達不到折半的效果配椭。因此，我們需要一個平衡的二叉搜索樹雹姊。
- 平衡二叉樹是通過對樹節(jié)點的左旋和右旋來保證樹的平衡性股缸，也就是保證左右子樹的高度差不超過 1。
- 在對樹進行左旋和右旋時吱雏，有四種形態(tài)分別是：左左敦姻，左右，右右歧杏，右左镰惦。因此，平衡二叉樹的查找犬绒、插入和刪除在平均和最壞情況下的時間復雜度都是O(log n)旺入。
1.7 紅黑樹
雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點，能夠把查找時間控制在 O(logn)凯力，不過卻不是最佳的茵瘾，因為平衡樹要求每個節(jié)點的左子樹和右子樹的高度差至多等于1劝萤，這個要求實在是太嚴了给猾，導致每次進行插入/刪除節(jié)點的時候，幾乎都會破壞平衡樹的第二個規(guī)則草穆，進而我們都需要通過左旋和右旋來進行調整祈惶，使之再次成為一顆符合要求的平衡樹雕旨。
顯然扮匠，如果在那種插入、刪除很頻繁的場景中奸腺，平衡樹需要頻繁著進行調整餐禁，這會使平衡樹的性能大打折扣，為了解決這個問題突照，于是有了紅黑樹帮非，紅黑樹具有如下特點：
- 節(jié)點是紅色或黑色。
- 根節(jié)點是黑色讹蘑。
- 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）末盔。
4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
- 從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點座慰。
下圖中這棵樹陨舱，就是一顆典型的紅黑樹：
image.png
紅黑樹自平衡的實現
紅黑樹節(jié)點的插入和刪除可能會破壞上述紅黑樹的性質并打破它的平衡，因此需要進行調整從而讓紅黑樹重新恢復平衡版仔；調整分兩種方式：旋轉以及變色游盲。
- 旋轉又分為左旋轉和右旋轉兩種形式：
左旋：如下圖所示以 P 為旋轉支點，旋轉支點 P 的右子節(jié)點 R 變?yōu)楦腹?jié)點蛮粮，其右子節(jié)點 R 的左子節(jié)點 RL 變?yōu)樾D支點 P 的右子節(jié)點益缎；左旋之后左子樹的節(jié)點相對旋轉之前要多出一個節(jié)點，也就是左子樹從右子樹借用一個節(jié)點然想；
image.png
/**
* 左旋示例代碼：
* P R
* / \ / \
* L R ====> P RR
* / \ / \
* RL RR L RL
* @param node 旋轉支點
*/
rotateLeft(node) {
// R
const rchild = node.right;
// P.right = RL
node.right = rchild.left;
// RL.parent = P;
if (rchild.left) {
rchild.left.parent = node;
}
// R.parent = P.paretn
rchild.parent = node.parent;
// 根節(jié)點情況莺奔，
if (!node.parent) {
this.root = rchild;
} else {
if (node === node.parent.right) {
// node 是父節(jié)點的右節(jié)點，
node.parent.right = rchild;
} else {
// node 是父節(jié)點的左節(jié)點变泄，
node.parent.left = rchild;
}
}
// R.left = P
rchild.left = node;
// P.parent = R;
node.parent = rchild;
}
右旋：如下圖所示以 R 為旋轉支點令哟，旋轉支點 R 的左子節(jié)點 P 變?yōu)楦腹?jié)點，而左子節(jié)點 P 的右子節(jié)點 RL 變?yōu)樾D支點 R 的左子節(jié)點妨蛹；右旋之后右子樹的節(jié)點相對旋轉之前要多出一個節(jié)點屏富，也就是右子樹從左子樹借用一個節(jié)點；
image.png
/**
* 右旋示例代碼：
* R P
* / \ / \
* P RR ====> L R
* / \ / \
* L RL RL RR
* @param node 旋轉支點
*/
rotateRight(node) {
// P
const lchild = node.left;
// R.left = RL ;
node.left = lchild.right;
// RL.parent = R
if (lchild.right) {
lchild.right.parent = node;
}
// P.parent = R.parent;
lchild.parent = node.parent;
// 根節(jié)點情況蛙卤，
if (!lchild.parent) {
this.root = lchild;
} else {
if (node === node.parent.right) {
// node 是父節(jié)點的右節(jié)點狠半，
node.parent.right = lchild;
} else if (node === node.parent.left) {
// node 是父節(jié)點的左節(jié)點，
node.parent.left = lchild;
}
}
// P.right = R;
lchild.right = node;
// R.parent = P;
node.parent = lchild;
}
- 變色就是由黑色節(jié)點變成紅色節(jié)點或者紅色節(jié)點變成黑色節(jié)點
image.png
節(jié)點插入
具體到實際應用中表窘，紅黑樹的節(jié)點是不能隨意旋轉和變色的典予，紅黑樹的旋轉和變色有方式方法甜滨，首先需要先找到插入節(jié)點的父節(jié)點位置乐严，與紅黑樹查找方式類似。本文以插入的節(jié)點為紅色為例衣摩，當然也可以用黑色節(jié)點作為插入節(jié)點昂验，但會更復雜捂敌。另外本文中所有節(jié)點中提的值都指的是 Key ，實際上節(jié)點還存在其它屬性既琴。
image.png
節(jié)點定義：
/**
* 節(jié)點
*/
class Node {
constructor(key, value, color = COLOR.RED) {
this.key = key;
this.value = value;
this.color = color;
this.left = null;
this.right = null;
this.parent = null;
}
}
節(jié)點插入及插入平衡操作
/**
* 插入key, value
*/
insert(key, value) {
if (this.root) {
// 紅黑樹為非空場景
let parent;
let node = this.root;
const newNode = new Node(key, value, COLOR.RED);
// 查找插入位置
while (node) {
parent = node;
if (key === node.key) {
// 場景二： 插入節(jié)點key已存在
newNode.color = node.color;
this.update(node, newNode);
return;
} else if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}
newNode.parent = parent;
if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
this.balanceInsertion(newNode);
} else {
// 場景一：紅黑樹為空樹場景
this.root = new Node(key, value, COLOR.BLACK);
}
}
// 插入節(jié)點平衡修正
balanceInsertion(node) {
// 場景三：插入節(jié)點的父節(jié)點為黑色節(jié)點占婉，無需修正
while (node.parent != null && node.parent.color === COLOR.RED) {
let uncle = null;
// 父節(jié)點是祖父節(jié)點左節(jié)點
if (node.parent === node.parent.parent.left) {
uncle = node.parent.parent.right;
// 場景四：叔叔節(jié)點為紅色
if (uncle != null && uncle.color === COLOR.RED) {
// 父節(jié)點、叔叔節(jié)點變成黑色甫恩，祖父節(jié)點變成紅色逆济，以祖父節(jié)點當作需要新節(jié)點繼續(xù)調用修正方法；
node.parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
node = node.parent.parent;
continue;
}
// 場景五：叔叔節(jié)點為空節(jié)點或者是黑色節(jié)點磺箕；
// 場景5.2 插入節(jié)點是父節(jié)點的右節(jié)點奖慌，先進行左旋轉換到場景5.1
if (node === node.parent.right) {
// 左旋之后，原插入節(jié)點的父節(jié)點變成新插入節(jié)點松靡；
node = node.parent;
this.rotateLeft(node);
}
// 場景5.1 插入節(jié)點是父節(jié)點的左節(jié)點简僧；
// 父節(jié)點變成黑色、祖父節(jié)點變成紅色
node.parent.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
// 對祖父節(jié)點右旋
this.rotateRight(node.parent.parent);
} else {
// 父節(jié)點是祖父節(jié)點右子節(jié)點
uncle = node.parent.parent.left;
// 場景四：叔叔節(jié)點為紅色
if (uncle != null && uncle.color === COLOR.RED) {
// 父節(jié)點雕欺、叔叔節(jié)點變成黑色岛马，祖父節(jié)點變成紅色，以祖父節(jié)點當作需要新節(jié)點繼續(xù)調用修正方法屠列；
node.parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
node = node.parent.parent;
continue;
}
// 場景5.4 插入節(jié)點是父節(jié)點的左節(jié)點啦逆，先進行右旋轉換到場景5.3
if (node === node.parent.left) {
// 右旋之后，原插入節(jié)點的父節(jié)點變成新插入節(jié)點脸哀；
node = node.parent;
this.rotateRight(node);
}
// 場景5.3插入節(jié)點是父節(jié)點的右節(jié)點蹦浦；
// 父節(jié)點變成黑色、祖父節(jié)點變成紅色
node.parent.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
// 對祖父節(jié)點左旋
this.rotateLeft(node.parent.parent);
}
}
this.root.color = COLOR.BLACK;
}
紅黑樹刪除
紅黑樹刪除操作包括兩部分撞蜂，一是查找到刪除節(jié)點盲镶，二是刪除節(jié)點以及刪除之后的自平衡。查找節(jié)點與二叉樹的查找方式一樣蝌诡。而刪除操作溉贿，當刪除節(jié)點不存在時，結束本次刪除操作浦旱；當刪除節(jié)點存在時宇色，刪除節(jié)點，然后找到一個節(jié)點替換已刪除的節(jié)點位置颁湖，重新連接上已刪除節(jié)點的父節(jié)點與孩子節(jié)點宣蠕。
總結
紅黑樹最吸引人的是它的所有操作在最差情況下可以保證 O(logN) 的時間復雜度，穩(wěn)定且高效甥捺。例如要在10 萬條(2^20)數據中查找一條數據抢蚀，只需要 20 次的操作就能完成。但這些保證有一個前置條件镰禾，就是數據量不大皿曲，且數據可以完全放到內存中唱逢。在數據量比較大時，因為紅黑樹的深度比較大造成磁盤 IO 的頻繁讀寫屋休，會導致它的效率低下坞古。
二、鏈表
2.1 反轉鏈表
//以鏈表的頭部節(jié)點為基準節(jié)點
//將基準節(jié)點的下一個節(jié)點挪到頭部作為頭節(jié)點
//當基準節(jié)點的next為null劫樟，則其已經成為最后一個節(jié)點痪枫，鏈表已經反轉完成
var reverseList = function (head) {
let currentNode = null;
let headNode = head;
while (head && head.next) {
currentNode = head.next;
head.next = currentNode.next;
currentNode.next = headNode;
headNode = currentNode;
}
return headNode;
};
2.2 復雜鏈表的復制
function Clone(pHead) {
if (pHead === null) {
return null;
}
cloneNodes(pHead);
cloneRandom(pHead);
return reconnetNodes(pHead);
}
function cloneNodes(pHead) {
var current = pHead;
while (current) {
var cloneNode = {
label: current.label,
next: current.next
};
current.next = cloneNode;
current = cloneNode.next;
}
}
function cloneRandom(pHead) {
var current = pHead;
while (current) {
var cloneNode = current.next;
if (current.random) {
cloneNode.random = current.random.next;
} else {
cloneNode.random = null;
}
current = cloneNode.next;
}
}
function reconnetNodes(pHead) {
var cloneHead = pHead.next;
var cloneNode = pHead.next;
var current = pHead;
while (current) {
current.next = cloneNode.next;
current = cloneNode.next;
if (current) {
cloneNode.next = current.next;
cloneNode = current.next;
} else {
cloneNode.next = null;
}
}
return cloneHead;
}
2.3 合并鏈表
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表叠艳，當然我們需要合成后的鏈表滿足單調不減規(guī)則听怕。
function Merge(pHead1, pHead2) {
if (!pHead1) {
return pHead2;
}
if (!pHead2) {
return pHead1;
}
let head;
if (pHead1.val < pHead2.val) {
head = pHead1;
head.next = Merge(pHead1.next, pHead2);
} else {
head = pHead2;
head.next = Merge(pHead1, pHead2.next);
}
return head;
}
2.4 鏈表環(huán)的入口節(jié)點
function EntryNodeOfLoop(pHead) {
if (!pHead || !pHead.next) {
return null;
}
let P1 = pHead.next;
let P2 = pHead.next.next;
// 1.判斷是否有環(huán)
while (P1 != P2) {
if (P2 === null || P2.next === null) {
return null;
}
P1 = P1.next;
P2 = P2.next.next;
}
// 2.獲取環(huán)的長度
let temp = P1;
let length = 1;
P1 = P1.next;
while (temp != P1) {
P1 = P1.next;
length++;
}
// 3.找公共節(jié)點
P1 = P2 = pHead;
while (length-- > 0) {
P2 = P2.next;
}
while (P1 != P2) {
P1 = P1.next;
P2 = P2.next;
}
return P1;
}
三、棧虑绵、隊列
棧：先進后出
隊列：先進先出
四尿瞭、哈希表|散列表
哈希的基本原理是將給定的鍵值轉換為偏移地址來檢索記錄。
哈希表在不出現哈希碰撞的基礎下時間復雜度是O(1), 出現哈希沖突解決方式有鏈式存儲翅睛、二度哈希
鍵轉換為地址是通過一種關系（公式）來完成的声搁，這就是哈希（散列）函數。
雖然哈希表是一種有效的搜索技術捕发，但是它還有些缺點疏旨。兩個不同的關鍵字，由于哈希函數值相同扎酷，因而被映射到同一表位置上檐涝。該現象稱為沖突。發(fā)生沖突的兩個關鍵字稱為該哈希函數的同義詞法挨。
image
如何設計哈希函數以及如何避免沖突就是哈希表的常見問題谁榜。 好的哈希函數的選擇有兩條標準：
- 簡單并且能夠快速計算
- 能夠在址空間中獲取鍵的均勻人分布
五、堆
堆的底層實際上是一棵完全二叉樹凡纳，可以用數組實現
- 每個的節(jié)點元素值不小于其子節(jié)點 - 最大堆
- 每個的節(jié)點元素值不大于其子節(jié)點 - 最小堆
堆在處理某些特殊場景時可以大大降低代碼的時間復雜度窃植，例如在龐大的數據中找到最大的幾個數或者最小的幾個數，可以借助堆來完成這個過程荐糜。
5.1 堆的構建
大頂堆
function ajustMaxHeap(array, index, length) {
for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
if (i + 1 < length && array[i + 1] > array[i]) {
i++;
}
if (array[index] >= [array[i]]) {
break;
} else {
[array[index], array[i]] = [array[i], array[index]];
index = i;
}
}
}
function createMaxHeap(arr, length) {
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
ajustMaxHeap(arr, i, length);
}
return arr;
}
小頂堆
function ajustMinHeap(array, index, length) {
for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
if (i + 1 < length && array[i + 1] < array[i]) {
i++;
}
if (array[index] < [array[i]]) {
break;
} else {
[array[index], array[i]] = [array[i], array[index]];
index = i;
}
}
}
function createMinHeap(arr, length) {
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
ajustMinHeap(arr, i, length);
}
return arr;
}
5.2 堆的插入
/*
由于堆屬于優(yōu)先隊列巷怜，只能從末尾添加
添加后有可能破壞堆的結構，需要從下到上進行調整
如果元素小于父元素暴氏，上浮
*/
function minHeapAdd(array = [], element) {
array.push(element);
if (array.length > 1) {
let index = array.length - 1;
let target = Math.floor((index - 1) / 2);
while (target >= 0) { array[target]);
if (array[index] < array[target]) {
[array[index], array[target]] = [array[target], array[index]]
index = target;
target = Math.floor((index - 1) / 2);
} else {
break;
}
}
}
return array;
}
5.3 堆的移除
/*
由于堆屬于優(yōu)先隊列延塑，只能從頭部移除
移除頭部后，使用末尾元素填充頭部答渔，開始頭部下沉操作
以小頂堆為例：
*/
function minHeapPop(array = []) {
let result = null;
if (array.length > 1) {
result = array[0];
array[0] = array.pop();
ajustMinHeap(array, 0, array.length);
} else if (array.length === 1) {
return array.pop();
}
return result;
}
六关带、圖
6.1什么是圖?
圖（graph），它表明了物件與物件之間的“多對多”的一種復雜關系研儒。圖包含了兩個基本元素：頂點（vertex, 簡稱V）和邊（edge, 簡稱E）豫缨。
有向圖與無向圖
如果給圖的每條邊規(guī)定一個方向，那么得到的圖稱為有向圖端朵。在有向圖中好芭，從一個頂點出發(fā)的邊數稱為該點的出度，而指向一個頂點的邊數稱為該點的入度冲呢。相反舍败，邊沒有方向的圖稱為無向圖。
有權圖與無權圖
如果圖中的邊有各自的權重敬拓，得到的圖是有權圖邻薯。比如地鐵路線圖，連接兩站的邊的權重可以是距離乘凸，也可以是價格厕诡，或者其他。反之营勤，如果圖的邊沒有權重灵嫌，或者權重都一樣（即沒有區(qū)分），稱為無權圖葛作。
連通圖
如果圖中任意兩點都是連通的寿羞，那么圖被稱作連通圖。圖的連通性是圖的基本性質赂蠢。無向圖中的一個極大連通子圖稱為其的一個連通分量绪穆。有向圖中，如果對任意兩個頂點Vi與Vj都存在i到j以及j到i的路徑虱岂，則稱其為強連通圖玖院，對應有強連通分量的概念。
圖的存儲
常用的存儲方式有兩種：鄰接矩陣和鄰接表第岖。
鄰接矩陣
image.png
采用一個大小為V*V的矩陣G司恳，對于有權圖，Gij可以表示Vi到Vj的邊的權重绍傲，如果是無權圖扔傅，則可設為1表示存在邊，0表示不存在邊烫饼。因此鄰接矩陣的表示相當的直觀猎塞，而且對于查找某一條邊是否存在、權重多少非掣茏荩快荠耽。但其比較浪費空間，對稠密圖（E>>V）來說比藻，會比較適合铝量。
image.png
鄰接表
G[N]為指針數組倘屹，對應矩陣每行一個鏈表，只存非零元素慢叨。
image.png
image.png
6.2 圖的遍歷
圖的遍歷最常用的有兩種：深度優(yōu)先搜索（Depth-first Search, DFS）和廣度優(yōu)先搜索（Breadth-First Search, BFS纽匙。
深度優(yōu)先搜索DFS
類似于樹的前序遍歷，即從一個選定的點出發(fā)拍谐，選定與其直接相連且未被訪問過的點走過去烛缔，然后再從這個當前點，找與其直接相連且未被訪問過的點訪問轩拨，每次訪問的點都標記為“已訪問”践瓷，就這么一條道走到黑，直到沒法再走為止亡蓉。沒法再走怎么辦呢晕翠？從當前點退回其“來處”的點，看是否存在與這個點直接相連且未被訪問的點砍濒。重復上述步驟崖面，直到沒有未被訪問的點為止。
image.png
廣度優(yōu)先搜索BFS
類似于樹的層序遍歷梯影，從一個選定的點出發(fā)巫员，將與其直接相連的點都收入囊中，然后依次對這些點去收與其直接相連的點甲棍。重復到所有點都被訪問然后結束简识。
image.png
6.3 最短路徑問題
在網絡中，求兩個不同頂點之間的所有路徑中感猛，邊的權值之和最小的那一條路徑
- 這條路徑就是兩點之間的最短路徑（Shortest Path）
- 第一個頂點為源點（Source）
- 最后一個頂點為終點（Destination）
問題主要分為：
單源最短路徑問題：從某固定源點出發(fā)七扰，求其到所有其他頂點的最短路徑。
多源最短路徑問題：求任意兩頂點間的最短路徑陪白。
單源最短路徑問題
無權圖的單源最短路算法颈走，可以借助BFS算法。
image.png
對于有向圖而言, 可以借助Dijkstra算法咱士。
Dijkstra算法的核心在于：從起點（或者說源點）開始立由，將其裝進一個“袋子”里，然后不斷往這個袋子里搜羅頂點序厉，當頂點收進去后锐膜，能保證從源點到該頂點的當前最短路徑是確定的。每次收錄的頂點是在未收錄的集合里尋找最短路徑最小的點（即離源點最近的點）弛房，然后將與收進去的頂點直接相連的點的最短路徑進行更新道盏。
image.png
image.png
多源最短路徑
image.png
image.png
void Floyd()
{
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
D[i][j] = G[i][j];
path[i][j] = -1;
}
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (D[i][k] + D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
// T =O(|V|^3)
參考
http://www.conardli.top/docs/
https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree
https://juejin.im/post/5dff59cb6fb9a0163c53ce1d#heading-11
https://zhuanlan.zhihu.com/p/37673101
https://www.icourse163.org/course/ZJU-93001
