堆的插入、删除、查看

深藏阁楼爱情的钟 2022-12-09 14:55 167阅读 0赞

堆，通常用数组来实现。用一个数组就可以表示一颗有有序的二叉树。

从大到小我们用A-Z来表示，越往后的字母表示越大

堆的定义：只要满足父节点大于子节点即可，左子节点和右子节点没有明确的顺序

堆的示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70][]

如果一个节点的位置为k(即索引值为k)，则它的父节点的位置为\[k/2\]，而它的两个子节点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在数中上下移动：从a\[k\]向上一层，就令k等于k/2，向下一层就令k等于2k或者2k+1，其中2k表示左子节点，2k+1表示右子节点

## 堆的插入 ##

如果直接插入新的元素，可能会打乱这个堆的顺序，所以需要用一种叫上浮的方法去调整它

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1][]

直到发现新插入的元素比父节点小，终止循环

这就是上浮方法插入元素

## 堆的删除 ##

堆的删除，只删除最大元素，也就是根节点。删除堆的元素的时候，也可能会破坏其有序性，所以，需要下沉的方法来调整

首先是把堆中最后一个元素与根节点交换，然后把根节点T删除

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 3][]

代码：

Heap类

package heap;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Heap<T extends Comparable<T>>{
    	//存储堆中的元素
    	public T[] items;
    	
    	public int N;
    	
    	public Heap(int capacity){
    		this.items = (T[]) new Comparable[capacity + 1];
    		this.N = 0;
    	}
    	
    	//判断堆中索引处 i 的元素是否小于索引处 j 的元素
    	public boolean less(int i, int j) {
    		return items[i].compareTo(items[j]) < 0;
    	}
    	
    	//交换堆中 i 索引和 j 索引处的值
    	public void exch(int i ,int j) {
    		T temp = items[i];
    		items[i] = items[j];
    		items[j] = temp;
    	}
    	
    	//在堆中插入一个元素
    	public void insert(T t) {
    		items[++N] = t;
    		swim(N);
    	}
    	
    	//使用上浮算法，使索引 k 处的元素能在堆中处于一个正确的位置
    	public void swim(int k) {
    		//通过循环，不断地比较当前节点的值和其父节点的值，如果发现父节点的值笔当前的节点值小，则交换位置
    		while(k > 1) {
    			//当前节点和其父节点
    			if(less(k/2, k)) {
    				exch(k/2, k);
    			}
    			k = k/2;
    		}
    	}
    	
    	//删除堆中最大的元素，并返回这个最大元素
    	public T delMax() {
    		T max = items[1];
    		//交换索引 1 处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根节点
    		exch(1, N);
    		//最大索引处的元素删除掉
    		items[N] = null;
    		//元素个数 -1
    		N--;
    		//通过下沉调整堆，让堆重新有序
    		sink(1);
    		
    		return max;
    	}
    	
    	//使用下沉算法，使索引 k 处的元素能在堆中处于一个正确的位置
    	public void sink(int k) {
    		//通过循环不断地对比当前k节点和其左子节点2*k 以及右子节点2k+1 处中的较大值的元素大小，如果当前节点小，则交换位置
    		while(2*k <= N) {
    			//获取当前的节点的子节点中的较大节点的值
    			int max;//记录较大节点所在的索引
    			if(2*k+1 <= N) {
    				if(less(2*k, 2*k + 1 )) {
    					max = 2*k + 1;
    				}else {
    					max = 2*k;
    				}
    			}else {
    				max = 2*k;
    			}
    			
    			
    			//比较当前的节点和较大节点的值
    			if(!less(k, max)) {
    				break;
    			}
    			//交换k索引处的值和max索引处的值
    			exch(k, max);
    			//交换k的值
    			k = max;
    		}
    		
    	}
    	
    	//获取Heap的所有元素
    	public List getHeap() {
    		List<T> list = new ArrayList<>();
    		for(int i=1;i<this.items.length;i++) {
    			list.add(items[i]);
    		}
    		return list;
    	}
    	
    	
    	
    }

HeapTest测试类

package heap;
    
    public class HeapTest {
    	public static void main(String[] args) {
    		//创建堆对象
    		Heap<String> heap = new Heap<String>(10);
    		//往堆中存入字符串数据
    		heap.insert("A");
    		heap.insert("S");
    		heap.insert("R");
    		heap.insert("P");
    		heap.insert("N");
    		heap.insert("O");
    		heap.insert("T");
    		heap.insert("E");
    		heap.insert("I");
    		heap.insert("H");
    		
    		//查看堆中所有的元素
    		System.out.println(heap.getHeap());
    				
    		//通过循环从堆中删除数据
    		String result = null;
    		while( (result = heap.delMax()) != null) {
    			System.out.print(result + "  ");
    		}
    		
    	}
    }

控制台输出

![20200922175734912.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70]: /images/20221123/a05b35a676fe4399bb6e98e39e68bb32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1]: /images/20221123/6b16f1a8112f4aa491ed0226b657a617.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 2]: /images/20221123/f6e58f13795440bd830882a5df05f372.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 3]: /images/20221123/3a68fa93ca484a659b89e1d455f29377.png
[20200922175734912.png]: /images/20221123/62e6947aa8d94419a8721ccca948157c.png