堆

堆和栈的区别

Java中的栈主要是用来存放八个基本数据类型的，以及方法调用的上下文。栈是与每一个线程相关联的，JVM在创建每一个线程，都会分配一定的栈空间给线程，主要存放线程执行过程中的局部变量。栈的空间会随着线程的终止而释放。

栈的优势存取速度要比堆更快，栈数据可以共享。缺点是存储在栈中的数据大小与生存期都是确定的，缺乏灵活性。

Java中的堆是所有的线程可以共享的一块内存区域。堆是用来存储各种Java的对象和数组的，是一个运行时数据区。堆是由垃圾回收来负责的，不需要程序代码来显式地释放。

堆的优势是可以动态地分配内存的大小，生存期也无需事先告知编译器，因为是在运行时动态分配内存的。Java的垃圾回收器会自动收走这些不再使用的数据。缺点是存取速度较慢，因为运行时要动态分配内存。

除此之外，静态存储区是主要存放静态数据、全局static数据和常量的。这块内存在程序编译时就已经分配好，并且在程序整个运行期间都存在。总的来说：堆和栈针对非静态数据，而方法区针对静态数据。

实现

• 堆是一个完全二叉树(除了最后一层，其他层从左到右的节点都是满的)
• 堆中的节点，都大于等于或小于等于其子节点
• 堆通常使用数组来存储

在这棵树中，所有父节点都满足大于等于其子节点的堆叫大根堆，所有父节点都满足小于等于其子节点的堆叫小根堆。堆虽然是一颗树，但是通常存放在一个数组中，父节点和孩子节点的父子关系通过数组下标来确定。

添加节点：

• 将新节点添加到树的末尾，即数组的末尾
• 再将插入的节点与其父节点做对比，如果父节点大于插入的节点，则交换二者的位置，直到插入的节点比父节点小为止

删除根节点：

删除根节点则是删除后再依次比较其与子节点的大小，直到找到新的父节点