数据结构基础15———非线性数据结构之堆(树堆)

树堆(英语:Treap),是有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树,Treap的特点是实现简单,且能基本实现随机平衡的结构。

Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树不同的是,Treap纪录一个额外的数据,就是优先级。Treap在以关键码构成二叉搜索树的同时,还满足堆的性质。Treap维护堆性质的方法用到了旋转,只需要两种旋转,编程复杂度比Splay要小一些。

堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。(见排序部分,另外但凡遇到求大量数据的前多少名,后多少名之类的问题第一个想到的就应该是对。和大量数据但是内存限制很小时马上想到hash一样...)

场景:
伸展树中我们把访问的放到根节点,但是我们不能保证最近访问的下一次优先级一定高啊(虽然概率比较大)。既然这样如果我知道一个优先级,能不能进行自定义呢?答案就是树堆了。

插入
给节点随机分配一个优先级,先和二叉搜索树的插入一样,先把要插入的点插入到一个叶子上,然后跟维护堆一样,如果当前节点的优先级比根大就旋转,如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。

由于旋转是O(1)的,最多进行h次(h是树的高度),插入的复杂度是O(h)的,在期望情况下h=O(log n),所以它的期望复杂度是O(logn)。

删除
因为Treap满足堆性质,所以只需要把要删除的节点旋转到叶节点上,然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子,向与其相反的方向旋转,直到那个节点被旋转到了叶节点,然后直接删除。

删除最多进行O(h)次旋转,期望复杂度是O(logn)。

查找
和一般的二叉搜索树一样,但是由于Treap的随机化结构,Treap中查找的期望复杂度是O(logn)。

只要满足这两点,它就是一个堆:
堆是一个完全二叉树;
堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

数组实现的堆(单纯的堆)
image.png
从图中我们可以看到,数组中下标为 i 的节点的左子节点,就是下标为 i∗2 的节点,右子节点就是下标为 i∗2+1 的节点,父节点就是下标为 2/i​ 的节点。知道了如何存储一个堆,那我们再来看看,堆上的操作有哪些呢?我罗列了几个非常核心的操作,分别是往堆中插入一个元素和删除堆顶元素。(如果没有特殊说明,我下面都是拿大顶堆来讲解)

  1. 往堆中插入一个元素往堆中插入一个元素后,我们需要继续满足堆的两个特性。
    如果我们把新插入的元素放到堆的最后,你可以看我画的这个图,是不是不符合堆的特性了?于是,我们就需要进行调整,让其重新满足堆的特性,这个过程我们起了一个名字,就叫作堆化(heapify)。堆化实际上有两种,从下往上和从上往下。这里我先讲从下往上的堆化方法。
    image.png
    堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。
    我这里画了一张堆化的过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,我们就互换两个节点。一直重复这个过程,直到父子节点之间满足刚说的那种大小关系。
    image.png
  2. 删除堆顶元素从堆的定义的第二条中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。假设我们构造的是大顶堆,堆顶元素就是最大的元素。当我们删除堆顶元素之后,就需要把第二大的元素放到堆顶,那第二大元素肯定会出现在左右子节点中。然后我们再迭代地删除第二大节点,以此类推,直到叶子节点被删除。这里我也画了一个分解图。不过这种方法有点问题,就是最后堆化出来的堆并不满足完全二叉树的特性。
    image.png
    因为我们移除的是数组中的最后一个元素,而在堆化的过程中,都是交换操作,不会出现数组中的“空洞”,所以这种方法堆化之后的结果,肯定满足完全二叉树的特性。
    image.png
public class Heap {
	
	// 数组,从下标 1 开始存储数据(单纯为了写着方便,也可以从0开始).a[i]节点的左子节点为a[2 * i],右子节点为a[2 * i + 1],兄弟节点为a[i + 1](如果不是根节点的话)
	private int[] arr; 
	private int maxCount; // 堆可以存储的最大数据个数
	private int count; // 堆中已经存储的数据个数

	public Heap(int capacity) {
		arr = new int[capacity + 1];
		maxCount = capacity;
		count = 0;
	}

	public void insert(int data) {

		if (count >= maxCount) {
			return;
		}

		count++;
		arr[count] = data;
		int i = count;
		// 如果新元素比父节点大 ---- 堆化
		while (i / 2 > 0 && arr[i] > arr[i / 2]) {
			// 交换两个节点,直到一个比插入节点大的节点为止
			int temp = arr[i];
			arr[i] = arr[i / 2];
			arr[i / 2] = temp;
			i = i / 2;
		}
	}

	public void removeMax() {
		//移除堆顶,重新构建大顶堆,堆化
		if (count == 0) {
			return;
		}

		arr[1] = arr[count];
		count--;
		heapify(arr, count, 1);
	}

	
	private void heapify(int[] arr, int n, int i) { // 自上往下堆化
		while (true) {
			int maxPos = i;
			if (i * 2 <= n && arr[i] < arr[i * 2]) {
				maxPos = i * 2;
			}
			if (i * 2 + 1 <= n && arr[maxPos] < arr[i * 2 + 1]) {
				maxPos = i * 2 + 1;
			}
			if (maxPos == i) {
				break;
			}
			int temp = arr[i];
			arr[i] = arr[maxPos];
			arr[maxPos] = temp;
			i = maxPos;
		}
	}
	
	
	private void buildHeap(int[] arr, int n) {
		  for (int i = n/2; i >= 1; --i) {
		    heapify(arr, n, i);
		  }
		}


}

基础问题:
1.数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

来源:力扣(LeetCode)215题

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

        // keep k largest elements in the heap
        for (int n: nums) {
          heap.add(n);
          if (heap.size() > k)
            heap.poll();
        }

        // output
        return heap.poll();        
  }
}

2.前 K 个高频元素
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

说明:
你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

来源:力扣(LeetCode)347题

 public List topKFrequent(int[] nums, int k) {
        List list=new ArrayList<>();
        if(nums.length==1){
        list.add(nums[0]);
            return list;
        }
        
        Map map=new HashMap<>();
        for(int i=0;i p=new PriorityQueue<>(map.size(), new Comparator() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    });
         for(Map.Entry entry:map.entrySet()){
             p.add(entry.getValue());
        } 
        int i=1;
        while(i<=k){
            int value=p.poll();
            int key=0;
            for(Map.Entry entry : map.entrySet()){
                if(entry.getValue().equals(value)){
                    key=entry.getKey();
                list.add(entry.getKey());
                break;
                } }
            map.remove(key);
            i++;
        }
        return list;
    }
}

更新时间:2020-02-13 15:36:59

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础15非线性数据结构之堆树堆
最后更新:2020-02-13 15:36:59

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×