java数据结构

JCF（java集合框架）

    接口interfaces

a.Collection接口说明

b.Map接口说明

2.类class

栈和队列：

都是线性表操作的子类

1.栈(Stack)LIFO:

a.顺序栈（基于数组）（数组末尾添加和删除元素即可）

b.链式栈（基于链表）

       核心操作:push pop peek

2.队列(Queue)FIFO：

a.链式队列（基于链表）

b.顺序队列——循环队列

       核心操作:offer poll peek

3.双端队列（Deque）:LinkedList

      
二叉树

1.前身：树：度 叶子结点 父节点 子节点 层次 高度深度 分支节点

树的表示形式：

Class Node{

       Int value;

       Node firstChild

       Node nextBrother

}

    特点：每个节点最多有两颗子树，即二叉树不存在度大于2的结点

二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树

    特殊的二叉树{ 满二叉树 完全二叉树}
    性质：1.第i层上最多有2^（i-1）

2.深度K最大的结点数2^k-1

3.n0=n2+1;

4.n个结点完全二叉树深度为log2(n+1)

5.存储：顺序存储

             链式存储：a。孩子表示法

                          b.孩子双亲表示法

6.遍历{前序 中序 后序}

7. 基本操作{preorderTraversal

InOrderTraversal

PostOrderTraversal

GetSize

GetLeafSize

getLevelSize}
堆（heap）

优先级队列——入队一样，出队不一样，按照优先级出队

普通队列：FIFO

    概念：堆是一颗完全二叉树（结构上）
    从节点值的要求

    最大堆：根节点的值一定不小于左右子树
    最小堆：根节点的值一定不大于左右子树

    堆的实现：（基本都是基于二叉树——二叉堆）

***最大堆—》根节点>=左右子树

                    层次和节点的大小没有任何关系***

相同数据可以构建成多种类型的堆（最大&最小）

    堆的表示——(数组)

堆的三大核心操作   //add(val)向堆中添加元素 siftUp(元素上浮)

                           //ectractMax():取出最大堆 siftDown(元素下沉)

                          //heapify 将任意一个数组堆化 add +siftDown

****原地堆排序***  O（nlogn）

    将任意数组heapify（siftDown） 调整为最大堆
    调整最大值与数组末尾的位置（siftDown 与之前不同：不考虑已交换元素）