数据结构 知识点

• 常见数据结构特征：

数据结构	特征
栈(stack)	先进后出
队列(queue)	先进先出
堆(heap)	按照一定的优先顺序排列，按照元素的优先级取出元素

• 堆(heap)
  堆是一种特殊的树，特殊表现在是完全二叉树，堆的通用特点就是父节点会大于或小于所有子节点。
  堆分为大顶堆和小顶堆，满足 Key[i] >= Key[2i+1] && key[i] >= key[2i+2] 称为大顶堆，满足 Key[i] <= key[2i+1] && Key[i] <= key[2i+2] 称为小顶堆。
  上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
  堆排序: 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。