邻接矩阵、邻接表都是图的基本存储方式，
稀松图情况下（即边远小于顶点情况下），用邻接表存储比较适合（相对矩阵N*N而言，邻接表只存储有值的边、顶点，不存储空值，存储效率更高）
稠密图情况下（即边远大地顶点情况下），用邻接矩阵存储比较适合（数据较多的情况下，要对较做遍历，如果用链表存储，要经常跳来跳去，效率较低）
堆：
几乎完全的二叉树：除了最右边位置上的一个或几个叶子可能缺少的二叉树。在物理存储上，可以用数组来存储，如果A[j]的顶点有左、右子节点，则左节点为A[2j]、右节点为A[2j+1]，A[j]的父顶点存储在A[j/2]中
堆：本身是一颗几乎完全的二叉树，而且父节点的值不小于子节点的值。应用场景：优先队列，寻找最大或次最大值；以及把一个新元素插入优先队列。
注：以下所有讨论的堆，约定索引0处的元素仅占位，有效元素从下标1开始
根据堆的定义，可以用以下代码测试一个数组是否为堆：
//测试数组H是否为堆 //(约定有效元素从下标1开始) //时间复杂度O(n) function isHeap(H) { if (H.length <= 1) { return false; } var half = Math.floor(H.length / 2); //根据堆的性质，循环上限只取一半就够了 for (var i = 1; i <= half; i++) { //如果父节点，比任何一个子节点 小，即违反堆定义 if (H[i] < H[2 * i] || H[i] < H[2 * i + 1]) { return false; } } return true; }
节点向上调整siftUp
某些情况下，如果堆中的某个元素值改变后(比如 10,8,9,7 变成 10,8,9,20 后，20需要向上调整 )，不再满足堆的定义，需要向上调整时，可以用以下代码实现
//堆中的节点上移 //(约定有效元素从下标1开始) function siftUp(H, i) { if (i <= 1) { return; } for (var j = i; j > 1; j = Math.floor(j / 2)) { var k = Math.floor(j / 2); //发现 子节点 比 父节点大，则与父节点交换位置 if (H[j] > H[k]) { var t = H[j]; H[j] = H[k]; H[k] = t; } else { //说明已经符合堆定义，调整结束，退出 return; } } }
节点向下调整siftDown (既然有向上调整，自然也有向下调整)
//堆中的节点下移 //(约定有效元素从下标1开始) //时间复杂度O(logN) function siftDown(H, i) { if (2 * i > H.length) { //叶子节点，就不用再向下移了 return; } for (var j = 2 * i; j < H.length; j = 2 * j) { //将j定位到 二个子节点中较大的那个上(很巧妙的做法) if (H[j + 1] > H[j]) { j++; } var k = Math.floor(j / 2); if (H[k] < H[j]) { var t = H[k]; H[k] = H[j]; H[j] = t; } else { return; } } }
向堆中添加新元素
//向堆H中添加元素x //时间复杂度O(logN) function insert(H, x) { //思路：先在数组最后加入目标元素x H.push(x); //然后向上推 siftUp(H, H.length - 1); }
从堆中删除元素
//删除堆H中指定位置i的元素 //时间复杂度O(logN) function remove(H, i) { //思路：先把位置i的元素与最后位置的元素n交换 //然后数据长度减1(这样就把i位置的元素给干掉了，但是整个堆就被破坏了) //需要做一个决定：最后一个元素n需要向上调整，还是向下调整 //依据：比如比原来该位置的元素大，则向上调整，反之向下调整 var x = H[i]; //先把原来i位置的元素保护起来 //把最后一个元素放到i位置 //同时删除最后一个元素(js语言的优越性体现!) H[i] = H.pop(); var n = H.length - 1; if (i == n + 1) { //如果去掉的正好是最后二个元素之一， //无需再调整 return ; } if (H[i] > x) { siftUp(H, i); } else { siftDown(H, i); } } //从堆中删除最大项 //返回最大值 //时间复杂度O(logN) function deleteMax(H) { var x = H[1]; remove(H, 1); return x; }
堆排序：
这是一种思路非常巧妙的排序算法，精华在于充分利用了“堆”这种数据结构本身的特点（首元素必然最大），而且每个元素的上移、下调，时间复试度又比较低，仅为O(logN)，空间上，也无需借助额外的存储空间，仅在数组自身内部交换元素即可。
思路：
1、先将首元素(即最大元素)与最末尾的元素对调---目的在于，把最大值沉底，下一轮重就不再管它了
2、经过1后，剩下的元素通常已经不再是一个堆了。这时，只要把新的首元素用siftDown下调，调整完以后，新的最大值元素自然又上升到了首元素的位置
3、反复1、2，大的元素逐一沉底，最后整个数组就有序了。
时间复杂度分析：创建堆需要O(n)的代价，每次siftDown代价为O(logN)，最多调整n-1个元素，所以总代价为 O(N) + (N-1)O(logN)，最终时间复杂度为O(NLogN)