目录
思考
◼ 设计一种数据结构，用来存放整数，要求提供 3 个接口
添加元素
获取最大值
删除最大值
三种情况是如下所示: 
堆的存在 ✓ 获取最大值：O(1)、删除最大值：O(logn)、添加元素：O(logn)
Top K问题------用堆来解决
什么是Top K问题?? 就是从海量的数据之中找出前K个数据
堆(Heap)
◼ 堆 （Heap）也是一种树状的数据结构（不要跟内存模型中的“堆空间”混淆），常见的堆实现有
二叉堆 （Binary Heap， 完全二叉堆 ）
多叉堆 （D-heap、D-ary Heap）
索引堆 （Index Heap）
二项堆 （Binomial Heap）
斐波那契堆 （Fibonacci Heap）
左倾堆 （Leftist Heap， 左式堆 ）
斜堆 （Skew Heap）
我们这里只学二叉堆
堆的一个重要性质是:任意节点的值总是>=(<=)子节点的值
◼ 堆的一个重要性质：任意节点的值总是 ≥ （ ≤ ） 子节点 的值
如果任意节点的值总是 ≥ 子节点 的值，称为： 最大堆 、 大根堆 、 大顶堆
如果任意节点的值总是 ≤ 子节点 的值，称为： 最小堆 、 小根堆 、 小顶堆 
堆中的元素必然是存在可比较性的.
堆的基本接口设计
接口的设计代码是如下所示:
public interface heap<E> {
int size();
boolean isEmpty();
void clear();
void add(E var1);
E get();
E remove();
E replace(E var1);
}
二叉堆(Binary Heap)
◼ 二叉堆 的逻辑结构就是一棵完全二叉树，所以也叫 完全二叉堆
◼ 鉴于完全二叉树的一些特性， 二叉堆 的底层（物理结构）一般用数组实现,使用数组直接存放相应的值.
◼ 索引 i 的规律（ n 是元素数量）
如果 i = 0 ，它是 根 节点
如果 i > 0 ，它的 父 节点的索引为 floor( (i – 1) / 2 )
如果 2i + 1 ≤ n – 1，它的 左 子节点的索引为 2i + 1
如果 2i + 1 > n – 1 ，它 无左 子节点
如果 2i + 2 ≤ n – 1 ，它的 右 子节点的索引为 2i + 2
如果 2i + 2 > n – 1 ，它 无右 子节点 
就是从上面到下面是依次减下的,直接是可以使用一个数组进行存放,就是不用数组进行存放了,不用杀鸡用牛刀.
最大堆的添加过程 
就是进行一个逐层交换的过程,循环.
循环执行以下操作(图中80简称是node)
如果 node ＞ 父节点
✓ 与父节点交换位置
如果 node ≤ 父节点，或者 node 没有父节点
✓ 退出循环
◼ 这个过程，叫做上滤（Sift Up） 专业术语
时间复杂度：O(logn)
此时进行一个框架的构建是如下所示:
import org.omg.CORBA.Object;
import java.util.Comparator;
public class BinaryHeap<E> extends AbstractHeap<E>{
private E[] elements;
private int size;
//如果要是需要进行扩容操作,那么就是需要使用一个相应的comparator
private Comparator<E> comparator;
//默认的容量进行一个使用
private static final int DEFAULT_CAPACITY = 10;
//传入comparator的过程
public BinaryHeap(Comparator<E> comparator)
{
super(comparator);
//进行一个声明,就是进行一个默认的大小的操作,并且进行相应的强制转换的过程使用.
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}
//要是不传入一个comparator的过程,就是进行相应的一个直接调用
public BinaryHeap()
{
this(null);
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public void clear() {
for(int i = 0;i < size;i++)
{
elements[i] = null;
}
size = 0;
}
@Override
public void add(E var1) {
elementNotNullCheck(var1);
ensureCapacity(size + 1);
elements[size++] = var1;
siftUp(size-1);
}
@Override
//拿到堆顶端元素的过程
public E get() {
emptyCheck();
return elements[0];
}
@Override
/**
* 进行删除的过程是删除的最大的值
*/
public E remove() {
return null;
}
@Override
public E replace(E var1) {
return null;
}
//进行一个上滤的过程
/**
* 让index位置的索引进行一个上滤的操作
* @param index
*/
private void siftUp(int index)
{
//
// //自己的这个元素只是需要拿到一次就是可以的
// E e = elements[index];
// while(index > 0)
// {
// int pindex = (index - 1) >> 1;
// E p = elements[pindex];
// if(compare(e,p) <= 0) return;
//
// //交换index,pindex位置的内容
// E temp = elements[index];
// elements[index] = elements[pindex];
// elements[pindex] = temp;
//
// //重新进行赋值操作,给index
// index = pindex;
// }
/**
* 对于上面的操作---交换过程进行一个优化
*/
//自己的这个元素只是需要拿到一次就是可以的
E e = elements[index];
while(index > 0) {
int pindex = (index - 1) >> 1;
E p = elements[pindex];
if (compare(e, p) <= 0) break;
//将父元素的存储位置在index的位置
elements[index] = p;
//重新进行赋值操作,给index
index = pindex;
}
elements[index] = e;
}
private void emptyCheck()
{
if(size == 0)
{
throw new IndexOutOfBoundsException("Heap is empty!!!!");
}
}
private void ensureCapacity(int capacity)
{
int oldCapacity = elements.length;
if(oldCapacity >= capacity) return;
//新增加的容量是原来的1.5倍数
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElement = (E[]) new Object[newCapacity];
for(int i = 0;i < size;i++)
{
newElement[i] = elements[i];
}
elements = newElement;
System.out.println(oldCapacity + "扩容到" + newCapacity);
}
private void elementNotNullCheck(E element)
{
if(element == null)
{
throw new IllegalArgumentException("element must not be null");
}
}
}
最大堆添加的优化过程---交换位置
如下所示的80这个元素,在进行相应的交换的时候,首先是将80这个元素提取出来,不进行相应的交换操作.
一般交换位置的代码是需要三行,但是这个地方是可以进行相应的优化的
将新添加的节点进行相应的备份,确定最终的位置才进行摆放上去
仅仅是从交换位置的代码优化过程可以得知,这里进行计算的时候所用的时间复杂度发生了改变
优化的代码段是如下所示:
private void siftUp(int index)
{
//
// //自己的这个元素只是需要拿到一次就是可以的
// E e = elements[index];
// while(index > 0)
// {
// int pindex = (index - 1) >> 1;
// E p = elements[pindex];
// if(compare(e,p) <= 0) return;
//
// //交换index,pindex位置的内容
// E temp = elements[index];
// elements[index] = elements[pindex];
// elements[pindex] = temp;
//
// //重新进行赋值操作,给index
// index = pindex;
// }
/**
* 对于上面的操作---交换过程进行一个优化
*/
//自己的这个元素只是需要拿到一次就是可以的
E e = elements[index];
while(index > 0) {
int pindex = (index - 1) >> 1;
E p = elements[pindex];
if (compare(e, p) <= 0) break;
//将父元素的存储位置在index的位置
elements[index] = p;
//重新进行赋值操作,给index
index = pindex;
}
elements[index] = e;
}父类的写法
创建一个AbstractHeap的父类,如下所示:
import org.omg.CORBA.Object;
import java.util.Comparator;
public abstract class AbstractHeap<E> implements heap<E>{
protected int size;
protected Comparator<E> comparator;
//传入comparator的过程
public AbstractHeap(Comparator<E> comparator)
{
this.comparator = comparator;
}
//要是不传入一个comparator的过程,就是进行相应的一个直接调用
public AbstractHeap()
{
this(null);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
protected int compare(E e1,E e2)
{
return comparator != null? comparator.compare(e1,e2)
:((Comparable<E>)e1).compareTo(e2);
}
}
删除操作
删除操作是首先将最后一个元素去覆盖掉相应的最大的地方,然后将最后一个元素进行相应的清空操作.如果要是最大的那个节点是比较小的(注意这里是进行比较下面的子节点的最大的家伙进行交换),就是一个不断进行交换的过程,知道得到的结果是符合的.代码思路是非常简单的.
删除的具体过程:------下滤(也是可以进行优化的)
1. 用最后一个节点覆盖根节点
2. 删除最后一个节点
3. 循环执行以下操作（图中的 43 简称为 node）
如果 node < 最大的子节点
✓ 与最大的子节点交换位置
如果 node ≥ 最大的子节点， 或者 node 没有子节点
✓ 退出循环
对于一个完全二叉树,叶子节点的个数n0=floor((n+1)/2),非叶子节点的个数是n1+n2=floor(n/2).完全二叉树的排列方式,只要排列下来,只要遇到第一个叶子节点,那么它的后面都是叶子节点.因此,只要是第一个叶子节点之前的,都是非叶子节点.
第一个叶子节点的索引就是非叶子节点的数量,在while进行判断的时候就是可以进行省略好多步骤.
删除操作的代码是如下所示:
@Override
/**
* 进行删除的过程是删除的最大的值
*/
public E remove() {
emptyCheck();
//进行一个size操作的整合
int lastIndex = --size;
//先将0这个位置的元素进行一个备份
E root = elements[0];
//将最后一个位置的元素覆盖0那个位置的元素
elements[0] = elements[lastIndex];
//将最后的一个元素进行相应的清空.
elements[lastIndex] = null;
//进行相应的一个下滤的操作siftDown()
siftDown(0);//就是让0这个位置的元素进行一个下滤的操作过程
return null;
}
下滤的代码是如下所示:
/**
* 进行下滤操作的一个过程
*/
private void siftDown(int index)
{
//将相应的最开始的那个节点的东西是需要放在一个位置的
E element = elements[index];
int half = size >> 1;
//while的条件是它含有子节点
//第一个叶子节点就是相应的非叶子节点的地方,直接进行相应的
while(index < half)//必须保证index位置是非叶子节点
{
//完全二叉树的子节点是存在两种情况:第一种情况:只有左子节点
//情况二:存在左右子节点
//默认是左子节点的索引
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
//右子节点
int rightIndex = childIndex + 1;
//选出左右子节点之中最大的,判断右子节点的存在
if(rightIndex < size && compare(elements[rightIndex],child) > 0)
{
// childIndex = rightIndex;
// child = elements[rightIndex];
//上面的两句进行一个整合,直接整合到一句上面
child = elements[childIndex = rightIndex];
}
if(compare(element,child) >= 0) break;
//将子节点放到相应的index的位置
elements[index] = child;
//重新设置index
index = childIndex;
}
elements[index] = element;
}replace操作
删除堆顶元素的时候,同时插入一个新的元素
为了节约时间,我们这里采用的方式是这样的,直接将所使用的元素直接进行相应的一个替代堆顶的元素,就是直接的一个logn的操作,不用两个logn了.
@Override
public E replace(E element) {
// E root = remove();
// add(element);
// return root;
//不推荐上面的做法,因为上面的是两个logn的操作,会使得非常的浪费时间
elementNotNullCheck(element);
E root = null;
//如果是没有任何东西的情况,直接就是一个进行替代的过程
if(size == 0)
{
elements[0] = element;
size ++;
}
else
{
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}最大堆-批量建堆(Heapify)
给你一组特别乱的数据,直接进行赶快建成一个数组的过程,就是称为批量建堆的过程.
- 第一种做法,就是将数据逐次使用一个添加的过程.
public class Main {
public static void main(String[] args) {
BinaryHeap<Integer> heap = new BinaryHeap<>();
int[] data = {88, 89, 90, 51, 52, 5};
for(int i = 0; i < data.length; i++)
{
heap.add(data[i]);
}
}
}- 方法二:自上而下的上滤
自上而下的上滤就是从上面开始进行建堆的过程.上面的过程是直接现在索引为一的位置开始(34开始),每当完成一个上滤就是进行执行的过程.
for(int i = 1 ;i < size;i++)
{
siftUp(i);
} - 方法三:自下而上的下滤
自下而上的下滤的进行过程注意,叶子节点是不需要进行的操作.需要首先拿到的是最后的一个非叶子节点的索引,第一个叶子节点的索引是size的一半,所以(size>>1)-1就是最后的一个非叶子节点的索引.
for(int i = (size >> 1) - 1; i >= 0;i--)
{
siftDown(i);
}- 从效率上面进行比较可以知道,自下而上的下滤操作的效率是比较高的.
效率对比的示意图是如下所示:
通过上面的对比可以知道,上滤过程计算的深度之和是O(nlogn),但是进行相应的下滤操作的过程相应的节点高度之和是O(n).公式一会儿再说,可以通过相应的公式进行证明.
- 复杂度的计算
针对于自上而下的上滤过程
◼ 所有节点的深度之和
√仅仅是叶子节点，就有近 n/2 个，而且每一个叶子节点的深度都是 O(logn) 级别的
√因此，在叶子节点这一块，就达到了 O(nlogn) 级别
√O(nlogn) 的时间复杂度足以利用排序算法对所有节点进行全排序
针对于自下而上的下滤操作
◼ 所有节点的高度之和
假设是满树，节点总个数为 n，树高为 h，那么 n = 2^ h − 1
所有节点的树高之和 H(n) = 2^ 0 ∗ （ h − 0） + 2^ 1 ∗ （ h − 1） + 2^ 2 ∗ （ h − 2 ） + ⋯ + 2^( h −1) ∗ （ h − (h − 1)）
H(n) = h ∗ (2^ 0 + 2^ 1 + 2^ 2 + ⋯ + 2^( h −1)) − [1 ∗ 2^ 1 + 2 ∗ 2^ 2 + 3 ∗ 2^ 3 + ⋯ + (h − 1) ∗ 2 h−1]
H(n) = h ∗ 2 h − 1 − h − 2 ∗ 2 h + 2
H(n) = h ∗ 2 h − h − h ∗ 2 h + 2 h+1 − 2
H(n) = 2^( h+1) − h − 2 = 2 ∗ (2^ h − 1) − h = 2n − h = 2n − log 2 (n + 1) = O(n)
公式推导
◼ S(h) = 1 ∗ 2 1 + 2 ∗ 2 2 + 3 ∗ 2 3 + ⋯ + h − 2 ∗ 2 h−2 + h − 1 ∗ 2 h−1
◼ 2S(h) = 1 ∗ 2 2 + 2 ∗ 2 3 + 3 ∗ 2 4 + ⋯ + h − 2 ∗ 2 h−1 + h − 1 ∗ 2 h
◼ S(h) – 2S(h) = [2 1 + 2 2 + 2 3 + ⋯ + 2 h−1 ] − h − 1 ∗ 2 h = (2 h − 2) − h − 1 ∗ 2 h
◼ S(h) = h − 1 ∗ 2 h − (2 h − 2) = h − 2 ∗ 2 h + 2
- 疑惑
为什么在建堆的过程之中,相应的自上而下的下滤和相应的自下而上的上滤是行不通的????
这是在本质上进行理解即可.
- 批量建堆
构造函数进行重构
//批量建堆的构造函数
public BinaryHeap(E[] elements,Comparator<E> comparator)
{
super(comparator);
if(elements == null || elements.length == 0)
{
this.elements = (E[])new Object[DEFAULT_CAPACITY];
}else{
size = elements.length;
//进行相应的一个建堆的过程
//最好不要将别人直接给的数组之间进行一个赋值的过程.
int capacity = Math.max(elements.length,DEFAULT_CAPACITY);//这里的容量的使用过程还是需要进行注意一下
this.elements = (E[])new Object[capacity];
for(int i = 0; i < elements.length;i++)
{
this.elements[i] = elements[i];
}
heapity();
}
}
//下面的几种情况都是调用第一个的过程,只是有的参数是不一样的
public BinaryHeap(E[] elements)
{
this(elements,null);
}
//传入comparator的过程
public BinaryHeap(Comparator<E> comparator)
{
this(null,comparator);
}
//要是不传入一个comparator的过程,就是进行相应的一个直接调用
public BinaryHeap()
{
this(null,null);
}批量建堆的函数
//批量建堆的函数
private void heapity()
{
// //方案一:自上而下的上滤------这种方法的效率是比较低的,因此我们一般是使用下面的这种方法
// for(int i = 1;i < size;i++)
// {
// siftUp(i);
// }
//方案二:自下而上的下滤
for(int i = (size >> 1) - 1;i >= 0;i--)
{
siftDown(i);
}
}如何构建一个小顶堆
通过重写compare的方式进行比较哪个返回值比较大的.返回大于0的数,认为是左边比较大,返回小于0的数,认为右边比较大.
Top K问题
◼ 从 n 个整数中，找出最大的前 k 个数（ k 远远小于 n ）
方案一: 如果使用排序算法进行全排序，需要 O(nlogn) 的时间复杂度
方案二: 如果使用二叉堆来解决，可以使用 O(nlogk) 的时间复杂度来解决
新建一个小顶堆
扫描 n 个整数
✓ 先将遍历到的前 k 个数放入堆中
✓ 从第 k + 1 个数开始，如果大于堆顶元素，就使用 replace 操作（删除堆顶元素，将第 k + 1 个数添加到堆中）
扫描完毕后，堆中剩下的就是最大的前 k 个数
static void test4() {
//步骤一:首先建立一个小顶堆
BinaryHeap<Integer> heap = new BinaryHeap(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
//步骤二:扫描n个数
//定义找出最大的前几个数
int k = 3;
Integer[] data = new Integer[]{51, 30, 39, 92, 74, 25, 16, 93, 91, 19, 54, 47, 73, 62, 76, 63, 35, 18, 90, 6, 65, 49, 3, 26, 61, 21, 48};
//先将遍历的K个数放到小顶堆之中
for(int i = 0; i < data.length; i++) {
if (heap.size() < k) {
heap.add(data[i]);
//如果要是k+1个数,就是将其进行一个置换操作
} else if (data[i] > (Integer)heap.get()) {
heap.replace(data[i]);
}
}
}◼ 如果是找出最小的前 k 个数呢？
用大顶堆
如果小于堆顶元素，就使用 replace 操作
完整代码
Heap接口
public interface heap<E> {
int size();
boolean isEmpty();
void clear();
void add(E var1);
E get();
E remove();
E replace(E var1);
}
AbstractHeap
import org.omg.CORBA.Object;
import java.util.Comparator;
public abstract class AbstractHeap<E> implements heap<E>{
protected int size;
protected Comparator<E> comparator;
//传入comparator的过程
public AbstractHeap(Comparator<E> comparator)
{
this.comparator = comparator;
}
//要是不传入一个comparator的过程,就是进行相应的一个直接调用
public AbstractHeap()
{
this(null);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
protected int compare(E e1,E e2)
{
return comparator != null? comparator.compare(e1,e2)
:((Comparable<E>)e1).compareTo(e2);
}
}
二叉堆实现代码
import com.sun.org.apache.xpath.internal.objects.XObject;
import org.omg.CORBA.Object;
import javax.swing.*;
import java.util.Comparator;
public class BinaryHeap<E> extends AbstractHeap<E>{
private E[] elements;
private int size;
//如果要是需要进行扩容操作,那么就是需要使用一个相应的comparator
private Comparator<E> comparator;
//默认的容量进行一个使用
private static final int DEFAULT_CAPACITY = 10;
//批量建堆的构造函数
public BinaryHeap(E[] elements,Comparator<E> comparator)
{
super(comparator);
if(elements == null || elements.length == 0)
{
this.elements = (E[])new Object[DEFAULT_CAPACITY];
}else{
size = elements.length;
//进行相应的一个建堆的过程
//最好不要将别人直接给的数组之间进行一个赋值的过程.
int capacity = Math.max(elements.length,DEFAULT_CAPACITY);//这里的容量的使用过程还是需要进行注意一下
this.elements = (E[])new Object[capacity];
for(int i = 0; i < elements.length;i++)
{
this.elements[i] = elements[i];
}
heapity();
}
}
//下面的几种情况都是调用第一个的过程,只是有的参数是不一样的
public BinaryHeap(E[] elements)
{
this(elements,null);
}
//传入comparator的过程
public BinaryHeap(Comparator<E> comparator)
{
this(null,comparator);
}
//要是不传入一个comparator的过程,就是进行相应的一个直接调用
public BinaryHeap()
{
this(null,null);
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public void clear() {
for(int i = 0;i < size;i++)
{
elements[i] = null;
}
size = 0;
}
@Override
public void add(E var1) {
elementNotNullCheck(var1);
ensureCapacity(size + 1);
elements[size++] = var1;
siftUp(size-1);
}
@Override
//拿到堆顶端元素的过程
public E get() {
emptyCheck();
return elements[0];
}
@Override
/**
* 进行删除的过程是删除的最大的值
*/
public E remove() {
emptyCheck();
//进行一个size操作的整合
int lastIndex = --size;
//先将0这个位置的元素进行一个备份
E root = elements[0];
//将最后一个位置的元素覆盖0那个位置的元素
elements[0] = elements[lastIndex];
//将最后的一个元素进行相应的清空.
elements[lastIndex] = null;
//进行相应的一个下滤的操作siftDown()
siftDown(0);//就是让0这个位置的元素进行一个下滤的操作过程
return null;
}
@Override
public E replace(E element) {
// E root = remove();
// add(element);
// return root;
//不推荐上面的做法,因为上面的是两个logn的操作,会使得非常的浪费时间
elementNotNullCheck(element);
E root = null;
//如果是没有任何东西的情况,直接就是一个进行替代的过程
if(size == 0)
{
elements[0] = element;
size ++;
}
else
{
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}
//批量建堆的函数
private void heapity()
{
// //方案一:自上而下的上滤------这种方法的效率是比较低的,因此我们一般是使用下面的这种方法
// for(int i = 1;i < size;i++)
// {
// siftUp(i);
// }
//方案二:自下而上的下滤
for(int i = (size >> 1) - 1;i >= 0;i--)
{
siftDown(i);
}
}
//进行一个上滤的过程
/**
* 让index位置的索引进行一个上滤的操作
* @param index
*/
private void siftUp(int index)
{
//
// //自己的这个元素只是需要拿到一次就是可以的
// E e = elements[index];
// while(index > 0)
// {
// int pindex = (index - 1) >> 1;
// E p = elements[pindex];
// if(compare(e,p) <= 0) return;
//
// //交换index,pindex位置的内容
// E temp = elements[index];
// elements[index] = elements[pindex];
// elements[pindex] = temp;
//
// //重新进行赋值操作,给index
// index = pindex;
// }
/**
* 对于上面的操作---交换过程进行一个优化
*/
//自己的这个元素只是需要拿到一次就是可以的
E e = elements[index];
while(index > 0) {
int pindex = (index - 1) >> 1;
E p = elements[pindex];
if (compare(e, p) <= 0) break;
//将父元素的存储位置在index的位置
elements[index] = p;
//重新进行赋值操作,给index
index = pindex;
}
elements[index] = e;
}
/**
* 进行下滤操作的一个过程
*/
private void siftDown(int index)
{
//将相应的最开始的那个节点的东西是需要放在一个位置的
E element = elements[index];
int half = size >> 1;
//while的条件是它含有子节点
//第一个叶子节点就是相应的非叶子节点的地方,直接进行相应的
while(index < half)//必须保证index位置是非叶子节点
{
//完全二叉树的子节点是存在两种情况:第一种情况:只有左子节点
//情况二:存在左右子节点
//默认是左子节点的索引
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
//右子节点
int rightIndex = childIndex + 1;
//选出左右子节点之中最大的,判断右子节点的存在
if(rightIndex < size && compare(elements[rightIndex],child) > 0)
{
// childIndex = rightIndex;
// child = elements[rightIndex];
//上面的两句进行一个整合,直接整合到一句上面
child = elements[childIndex = rightIndex];
}
if(compare(element,child) >= 0) break;
//将子节点放到相应的index的位置
elements[index] = child;
//重新设置index
index = childIndex;
}
elements[index] = element;
}
private void emptyCheck()
{
if(size == 0)
{
throw new IndexOutOfBoundsException("Heap is empty!!!!");
}
}
protected int compare(E e1,E e2)
{
return comparator != null? comparator.compare(e1,e2)
:((Comparable<E>)e1).compareTo(e2);
}
private void ensureCapacity(int capacity)
{
int oldCapacity = elements.length;
if(oldCapacity >= capacity) return;
//新增加的容量是原来的1.5倍数
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElement = (E[]) new Object[newCapacity];
for(int i = 0;i < size;i++)
{
newElement[i] = elements[i];
}
elements = newElement;
System.out.println(oldCapacity + "扩容到" + newCapacity);
}
private void elementNotNullCheck(E element)
{
if(element == null)
{
throw new IllegalArgumentException("element must not be null");
}
}
}
本文含有隐藏内容，请 开通VIP 后查看