您的当前位置：首页正文

Java——堆

2024-11-07 来源：个人技术集锦

一、什么是堆

九月在老家是收割水稻的月份，每次打完水稻，农民伯伯就会拿稻杆累成一堆。我觉得这个稻杆堆和数据结构堆外形有点相似哈。

二、堆的存储方式

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。对于非完全二叉树，则不适合使用顺序方式进行存储。

如果i=0，则i表示为根节点，否则i结点的双亲为（i-1）/ 2
对于i，如果 i * 2 + 1 小于数组的长度，则i的左孩子为 i * 2 + 1，否则无左孩子。
对于i，如果 i * 2 + 2 小于数组的长度，则i的右孩子为 i * 2 + 2，否则无右孩子。

三、堆的创建

堆的创建有两种方式：向下调整和向上调整。

向下调整

对于一个不是堆的任意一个数组，采用向下调整为大根堆我们可以这样做：
先调整最下面的每一层子二叉树变大根堆，再一层一层往上面调整，那么整棵树到最后也就变为大根堆了。

1.先找到最后一个根结点 (叫child结点），再找child的父节点（叫parent 结点）。
2.比较父结点与左右孩子结点中最大的孩子结点的大小，如果大于最大孩子结点则不交换，小于则交换两结点 parent=child,child=child*2+1 同时child 要在数组有效数据的范围内。
parent - -，重复2，parent要在数组范围内。

public class TestHeap {
	//堆存在一维数组elem中
    public int[] elem;
    //堆中的元素个数
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    
    //先初始化数组
    public void  initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

	//创建堆
    public void createHeap() {
    //先调整最下面的每一层子二叉树变大根堆，再一层一层往上面调整。
        for (int parent = (elem.length-1-1)/2; parent >= 0 ;parent--) {
        
            siftDown(parent,this.usedSize);
        }

    }
//向下调整
    private void siftDown(int parent, int usedSize) {
    
        int child = parent*2+1;
        
        // child要在堆内
        while(child<usedSize) {
        
        //求出左右孩子中最大的孩子
            if(child+1<usedSize && elem[child]<elem[child+1]) {
                child++;
            }
            
            if(elem[child]>elem[parent]) {
                //大于就交换
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                
                //再看下其孩子树是否要交换
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }

    }
    //打印elem数组
        public void printElem() {
        System.out.println(Arrays.toString(elem));
    }

    public static void main(String[] args) {
        int[] arr = {27,15,19,18,28,34,65,49,25,37};
        TestHeap heap = new TestHeap();
        heap.initElem(arr);
        heap.createHeap();
        heap.printElem();

    }
   }

如果想要得到小根堆，就只需求得左右孩子最小，在与父结点相比，如果父结点大则交换，否则不交换。

向上调整

因为向上调整是堆的插入的一个步骤，所以在后面写到。

四、堆的时间复杂度——图是高博Teacher的

向下调整建堆的时间复杂度为O(n)。向下调整建堆也是一般常用的建堆方法。

五、堆的插入与删除

堆的插入：

1. 将最后新插入的节点向上调整，直到满足堆的性质。

1.先找到最后一个根结点 (叫child结点），再找child的父节点（叫parent 结点）。
2.比较父结点与左右孩子结点中最大的孩子结点的大小，如果大于最大孩子结点则不交换，小于则交换两结点 child = parent,parent=(parent-1)/2 同时child 要>0。

//插入数据
public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[this.usedSize] = val;
        siftUp(usedSize);
        this.usedSize++;
    }
//向上调整
    private void siftUp(int usedSize) {
        int child = usedSize;
        int parent = (usedSize-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (parent-1)/2;
            }else {
                break;
            }

        }



    }
//判断数组是否满
    private boolean isFull() {

        return usedSize==elem.length;
    }

如果想让向上调整一个不是堆结构的数组为堆，就要一个一个数据的插入。
向上调整也可以调整为小根堆的。

堆的删除
堆的删除一定删除的是堆顶元素。
具体如下：

将堆顶元素对堆中最后一个元素交换
将堆中有效数据个数减少一个
对堆顶元素进行向下调整

常见习题

1.下列关键字序列为堆的是:()
A: 100,60,70,50,32,65
B: 60,70,65,50,32,100
C: 65,100,70,32,50,60
D: 70,65,100,32,50,60

2.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()
A: 1 B: 2 C: 3 D: 4

3.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是()
A: [3，2，5，7，4，6，8]
B: [2，3，5，7，4，6，8]
C: [2，3，4，5，7，8，6]
D: [2，3，4，5，6，7，8]

[参考答案]
1.A
2.C

3.C

完整代码

package Tree;

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    public void  initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }
    
    public void createHeap() {
        for (int parent = (elem.length-1-1)/2; parent >= 0 ;parent--) {
            siftDown(parent,this.usedSize);
        }

    }

    //向下调整
    private void siftDown(int parent, int usedSize) {

        int child = parent*2+1;
        while(child<usedSize) {
            if(child+1<usedSize && elem[child]<elem[child+1]) {
                child++;
            }
            if(elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * child + 1;
            }else {
                break;
            }
        }

    }
 
    //简单打印数组
    public void printElem() {
        System.out.println(Arrays.toString(elem));
    }

   //插入元素
    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[this.usedSize] = val;
        siftUp(usedSize);
        this.usedSize++;
    }
    //向上调整
    private void siftUp(int usedSize) {
        int child = usedSize;
        int parent = (usedSize-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (parent-1)/2;
            }else {
                break;
            }
        }

    }

    public boolean isFull() {

        return usedSize==elem.length;
    }
    //出堆头元素
    public int poll() {
        if(isEmpty()) {
            return -1;// 抛出异常
        }
        int tmp = elem[usedSize-1];
        elem[usedSize-1] = elem[0];
        elem[0] = tmp;
        usedSize--;
        siftDown(0,usedSize);
        return tmp;
    }

    public boolean isEmpty() {

        return usedSize==0;
    }
    //取堆头元素
    public int peek() {
        if(isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    public static void main(String[] args) {
        int[] arr = {27,49,65,25,37,34,19,18,15,28};
        TestHeap heap = new TestHeap();
        heap.initElem(arr);
        heap.createHeap();
        heap.printElem();
        //80入堆
        heap.push(80);
        heap.printElem();
        //80出堆
        heap.poll();
        heap.printElem();
    }
    
}