接着引入的思想讲,
堆是一种抽象的数据结构,不管什么计算机二进制内存什么的,我们可以把堆画成一个完全二叉树。
完全二叉树?给一下严谨定义:
满二叉树就是完完全全完整的一棵树,如果有n层的话,那么就有2^n-1^个节点,完全二叉树就是可以在满二叉树上的基础上缺少,只能缺少最后一排的右边,左边必须连续排列。
堆是一种抽象结构,那把他在内存中具象化是什么样子呢?有些树是通过左右指针实现的,但是堆是通过数组实现的,你观察一下就能发现,如果把根在数组中的下标是n,那么一个节点的的左子节点就是这个节点的2n,右子节点就是2n+1。
最大堆就是父亲节点比子节点大,这样从上到下就越来越小,最小堆反之。
继续拿最大堆说,假如秩序井然的最大堆出现了一个害群之马,他比他父节点还要大,(这里不用管他和兄弟节点的关系,首先他兄弟比父亲小,肯定也比他小,也不用考虑和他子节点的关系,他都比他爸还要大了),那就让他和他父亲交换位置,交换之后他又比他新爸爸还大?那继续交换,直到根节点,从抽象看,这个节点一直都在上升,我们称之为swin上浮。
反过来,害群之马比子节点小呢?这时候为了恢复秩序,就要和子节点交换了,这里就要多一个考虑有两个子节点,如果他只比其中一个小,好办,她两交换,他比两个子节点都小怎么办?把子节点里面大的那个换上去,不然还是恢复不了秩序,重复以此直到换到树叶上,我们称之为下潜sink。
你这个堆就能保证每次只有一匹害群之马?
是的,在加入和删除的时候出现,
加入元素时,直接放到最后一层最左边,让他去上浮。
删除元素时(这里指删除根节点,)把根节点扣了,把最后一个节点拿上来,然后让他下潜。
最后我们发现,这种数据结构能够自动维护数组的最大值,即使数组一直进进出出。只看他的功能,我们不管抽象结构和上浮下潜,那就可以叫他优先队列。
这就是 抽象 >> 具象 >> 只关心功能。