哈希队列栈链表树

哈希（Hash）

特点：
计数排序中的桶（复杂度 O(n+max)，比快排还快
桶排序 与计数排序的区别
基数排序 与计数排序的区别

形式：
key : value

计数排序
比较排序：冒泡排序、选择排序、插扑克牌 。（NlogN）

队列（Queue）：

特点：先进先出
实现：可以用数组实现
举例：排队、12306订票（先买票的人先出票）

var q=[]
q.push('张三','李四','王五','赵六')
q.shift()

栈（Stack）

特点：先进后出
实现：可以用数组实现
举例：盗梦空间、坐电梯（先进去的人站最里面）

var stack=[]
stack.push('张三','李四','王五','赵六')
stack.pop()

名称	进	出	实现
队列	push	shift	数组
栈	push	pop	数组

• 数组既可以当队列又可以当栈，数组是哈希。

链表（Linked List）（一般用不到）

数组无法直接删除中间的一项，链表可以
用哈希（JS里面用对象表示哈希）实现链表，链表是动态的
head、node 概念
链表的第一个哈希对象head，找到表头就能找到后边的所有项。其他的叫做节点node，表头也叫做节点。

var a = {
    value:0,
    next:{
        value:2,
        next:{
            value:1,
            next:undefined
        }
    } 
}

image.png

综上可见：

• 数组 删除很慢，复杂。
• 链表 查询很慢，要一直next.next.next。
• 不经常删除或者只删头尾时用「 数组 」
• 经常从中间删除一个东西就用链表，一般不会有这样的需求，所以链表也很少用。
• 一般都用队列或栈，都是用数组实现的。

树（tree）

• 举例：层级结构、DOM

• 概念：层数、深度、节点个数

• 二叉树

• 满二叉树

• 完全二叉树

• 完全二叉树和满二叉树可以用数组实现

  
  image.png

• 其他树可以用哈希（对象）实现

• 操作：增删改查

• 堆排序用到了 tree

• 其他：B树、红黑树、AVL树

堆排序可视化：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

堆排序JS代码完整讲解（看到最后）：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/