AK F.*ing leetcode 流浪计划之堆

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

@[toc]

一、简介

堆数据结构是一种数据选择器,基于其的排序算法其实是一种选择排序。堆在平时的算法中非常常用,也是go语言操作的基础算法。在面试中也经常被问到其原理,甚至会让手写堆排序。学习与解理堆算法原理,不管是对于语言排序源码的理解,还是解决算法题都是非常有帮助的。防止在面试时眼高手低。

由于堆实现在各语言中都有,这里主要以int为例,讲解堆原理,以及排序的实现。最后结合题目讲解堆的应用。

本文中堆原理参照严版《数据结构与算法》,公众号内回复“数据结构”可以获取pdf电子版。

二、定义

堆是一种完全二叉树数据结构。

其性质是二叉树中的每个子树,根的值总是要比孩子的值要大(大顶堆)。

堆有大顶堆与小顶堆之分,以堆顶元素是所有元素中最大或最小为区分。

完全二叉树在表示时我们可以用数组来表示(下标从1开始),结点i的2个孩子(如果有)分别2*i, 2*i+1。

堆的主要操作有,初始化堆,向下调整,向上调整,删除堆顶元素,添加一个元素。

三、作用

  1. 对元素进行排序。
  2. 快速选择最优值(最小,最大,条件最优等,dijkstra最短路应用)。
  3. 取集合中前K大元素。
  4. 通过定义多维条件,快速选择出最优解。

四、数据定义及算法

堆是一种完全二叉树数据结构。我们以下将以大顶为进行讲解。

在表示时我们可以用数组来表示(下标从1开始),结点i的2个孩子(如果有)分别2*i, 2*i+1。

数据定义

Heap {
    arr array // 数组 结点i的2个孩子(如果有)分别2\*i, 2*i+1。编号从1开始
    // 主要操作:
    down(i):// 向下调整 
    up(i) // 向上调整 down, up是堆的基础操作,作用是在堆发生变化时,对堆进行调整,使得堆满足其性质
    Init(): // 初始化数据,通过多次调用down操作,使得数组满足堆的性质
  	Pop() // 弹出堆顶
	  Push(x) // 添加元素
}

算法描述

down(i): // 向下调整, 如图1
	pivot <- arr[i]
	while i*2<len(arr) : // 有子孩子
		child <- i*2
		如果有右孩子且右孩子值比左孩子大 child++
		如果孩子是否比根大:arr[i]<-arr[child], i <- child // 将根下移
		否则 break
	
	// 最后要把pivot赋值给最终根
	arr[i]<-pivot
		

up(i): // 向上调整, 如图2
	pivot <- arr[i]
	while i/2 > 0 &&  arr[i/2]<pivot : // 有父结点且父值比自己的小
		arr[i]<-arr[i/2]
		i <- i/2
	
	// 最后要把pivot赋值给最终根
	arr[i]<-pivot
		

Init(arr): // 初始化数据,构建初始堆
    // 从n/2 编号开始,依次向下调整
    // 当调整至i,时i的所有子树已经调整完毕,所以只要关注arr[i]的位置,就可以使子树i形成堆。
    for i <- (len(arr)-1)/2 to 1 do
        down(i)

Pop():// 删除堆顶元素
	pivot <- arr[1]
	arr[1]<-arr[len(arr)-1] // 将最后一个值放到根
	arr <- arr[0:len(arr)-1] // 缩短最后一个空间
  
  down(1) // 向下调整
  return pivot


Push(x):// 添加元素
	arr <- append(arr, x)// 将最后一个值放到根
    up(len(arr)-1) // 向上调整



五、具体实现

package main
import "fmt"

type Heap struct {
	arr []int // 数组 结点i的2个孩子(如果有)分别2\*i, 2*i+1。编号从1开始
}

func (h *Heap) down(i int) { // 向下调整
	if i> h.Len() {return}
	pivot := h.arr[i]
	for i*2 <= h.Len() { // 有子孩子
		child := i * 2
		// 如果有右孩子且右孩子值比左孩子大
		if child+1 <= h.Len() && h.arr[child+1] > h.arr[child] {
			child++
		}

		// 如果孩子是否比根大:arr[i] <- arr[child], i <- child // 将根下移
		if h.arr[child] > pivot {
			h.arr[i], i = h.arr[child], child
		} else {
			break
		}

	}
	// 最后要把pivot赋值给最终根
	h.arr[i] = pivot
}

func (h *Heap) up(i int) { // 向上调整 down, up是堆的基础操作,作用是在堆发生变化时,对堆进行调整,使得堆满足其性质
	pivot := h.arr[i]
	for i/2 > 0 && h.arr[i/2] < pivot { // 有父结点且父值比自己的小
		h.arr[i], i = h.arr[i/2], i/2
	}

	// 最后要把pivot赋值给最终根
	h.arr[i] = pivot
}

func (h *Heap) Init(arr []int) { // 初始化数据,构建初始堆
	h.arr = append([]int{0}, arr...) // 第1个空元素,有效编号从1开始
	// 从n/2 编号开始,依次向下调整
	// 当调整至i,时i的所有子树已经调整完毕,所以只要关注arr[i]的位置,就可以使子树i形成堆。
	for i := h.Len()/ 2; i > 0; i-- {
		h.down(i)
	}
}

func (h *Heap) Len() int { // 获取元素个数
	if len(h.arr) < 2 {
		return 0
	}
	return len(h.arr) - 1
}

func (h *Heap) Pop() int { // 删除堆顶元素
	if h.Len() == 0 {
		panic("len == 0")
	}
	pivot := h.arr[1]
	h.arr[1] = h.arr[h.Len()]  // 将最后一个值放到根
	h.arr = h.arr[0 : h.Len()] // 缩短最后一个空间

	h.down(1) // 向下调整
	return pivot
}

func (h *Heap) Push(x int) { // 添加元素
	h.arr = append(h.arr, x) // 将最后一个值放到根
	h.up(h.Len())     // 向上调整
}

// 排序实现
func Sort(arr []int) []int{
	h := &Heap{}
	h.Init(arr)

	for i:=len(arr)-1;h.Len()>0;i-- {
		arr[i]=h.Pop() // 从大到小赋值
	}

	return arr
}

func main() {
   fmt.Println(Sort([]int{10,6,7,12,18,12,1,2,4,3}))
}

复杂度分析,每次up或down 都是二叉树高度,也就是 log(n), 堆的初始化是 nlog(n), 每次插入或删除是log(n)

以上代码只是为了理解堆排序原理作的简单实现,扩展性不好,实际应用可以直接使用go语言库。

六、牛刀小试

练习1 验证代码是否正确,排序应用

题目链接 力扣

题目大意

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

题目解析

原意是希望选手使用链表,这里是为了验证本文代码正确性。先转化成数组,然后利用堆排序,再赋值回链表。

AC代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type Heap struct {
	arr []int // 数组 结点i的2个孩子(如果有)分别2\*i, 2*i+1。编号从1开始
}

func (h *Heap) down(i int) { // 向下调整
	if i> h.Len() {return}
	pivot := h.arr[i]
	for i*2 <= h.Len() { // 有子孩子
		child := i * 2
		// 如果有右孩子且右孩子值比左孩子大
		if child+1 <= h.Len() && h.arr[child+1] > h.arr[child] {
			child++
		}

		// 如果孩子是否比根大:arr[i] <- arr[child], i <- child // 将根下移
		if h.arr[child] > pivot {
			h.arr[i], i = h.arr[child], child
		} else {
			break
		}

	}
	// 最后要把pivot赋值给最终根
	h.arr[i] = pivot
}

func (h *Heap) up(i int) { // 向上调整 down, up是堆的基础操作,作用是在堆发生变化时,对堆进行调整,使得堆满足其性质
	pivot := h.arr[i]
	for i/2 > 0 && h.arr[i/2] < pivot { // 有父结点且父值比自己的小
		h.arr[i], i = h.arr[i/2], i/2
	}

	// 最后要把pivot赋值给最终根
	h.arr[i] = pivot
}

func (h *Heap) Init(arr []int) { // 初始化数据,构建初始堆
	h.arr = append([]int{0}, arr...) // 第1个空元素,有效编号从1开始
	// 从n/2 编号开始,依次向下调整
	// 当调整至i,时i的所有子树已经调整完毕,所以只要关注arr[i]的位置,就可以使子树i形成堆。
	for i := h.Len()/ 2; i > 0; i-- {
		h.down(i)
	}
}

func (h *Heap) Len() int { // 获取元素个数
	if len(h.arr) < 2 {
		return 0
	}
	return len(h.arr) - 1
}

func (h *Heap) Pop() int { // 删除堆顶元素
	if h.Len() == 0 {
		panic("len == 0")
	}
	pivot := h.arr[1]
	h.arr[1] = h.arr[h.Len()]  // 将最后一个值放到根
	h.arr = h.arr[0 : h.Len()] // 缩短最后一个空间

	h.down(1) // 向下调整
	return pivot
}

func (h *Heap) Push(x int) { // 添加元素
	h.arr = append(h.arr, x) // 将最后一个值放到根
	h.up(h.Len())     // 向上调整
}

func Sort(arr []int) []int{
	h := &Heap{}
	h.Init(arr)

	for i:=len(arr)-1;h.Len()>0;i-- {
		arr[i]=h.Pop()
	}

	return arr
}

func sortList(head *ListNode) *ListNode {
	arr := []int{}
	for t:=head;t!=nil;t=t.Next {
		arr  = append(arr, t.Val)
	}

	arr = Sort(arr)
	for t:=head;t!=nil;t=t.Next {
		t.Val = arr[0]
		arr = arr[1:]
	}
	
	return head
}

练习2 利用小顶堆求丑数

题目链接:力扣

题目大意

给你一个整数 n ,请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1:

输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:

输入:n = 1
输出:1
解释:1 通常被视为丑数。

提示:

1 <= n <= 1690

题目解析

每个丑数x, 都可以产生出3个丑数 x*2, x*3, x*5,产生后往池(丑数池里)里加。

下一个丑数是丑数池里最小的数。

从1开始 → 2,3,5

下一个选择的是2, 由于3,5都还未被选择到,所以以3,5为乘数的丑数是不可能被选择的。

AC代码

type myHeap []int

func (h *myHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}

func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
	return len(*h)
}

func (h *myHeap) Pop() (v interface{}) {
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}

func (h *myHeap) Push(v interface{}) {
	*h = append(*h, v.(int))
}

func nthUglyNumber(n int) int {
	h:= &myHeap{}
	heap.Push(h, 1) // 先加入1

	ans :=0
	for ;n>0;n-- {
		top := heap.Pop(h).(int)
		for top==ans {
			top = heap.Pop(h).(int)
		}
		ans = top
		//fmt.Println(ans)
    // 每产生一个丑数,就加入以该丑数为底数的更大的丑数
		heap.Push(h, ans*2)
		heap.Push(h, ans*3)
		heap.Push(h, ans*5)
	}

	return ans
}


练习3 利用条件构造解决复杂问题

题目链接:力扣

题目大意

给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个长度至少为 3 的子序列,其中每个子序列都由连续整数组成。

如果可以完成上述分割,则返回 true ;否则,返回 false 。

示例 1:

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5
示例 2:

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5
示例 3:

输入: [1,2,3,4,4,5]
输出: False

提示:

1 <= nums.length <= 10000

题目解析

定义数组 d[],表示一个以d[0]结尾并且长度d[1]的序列。

遍历数组,去构造序列,每遇到一个数字x,优先查看是不可以加入到之前构造出来的序列。

利用贪心原理,优先查找d[0]=x-1, 并且d[1]最小的d. 这就可以通过堆来实现。

AC代码

type myHeap [][2]int

func (h *myHeap) Less(i, j int) bool {
	if (*h)[i][0] != (*h)[j][0] {
		return (*h)[i][0] < (*h)[j][0]
	} // 先取结尾数小的
	return (*h)[i][1] < (*h)[j][1] // 再取连续个数最小的
}

func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
	return len(*h)
}

func (h *myHeap) Pop() (v interface{}) {
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}

func (h *myHeap) Push(v interface{}) {
	*h = append(*h, v.([2]int))
}

func isPossible(nums []int) bool {
	h := &myHeap{} // 大顶堆

	for _, v := range nums {
				
    		// 根据条件,不一定每次都取到 d[0]=x-1, 所以要循环
        for h.Len()>0 {
            top := heap.Pop(h).([2]int)
            if top[0]==v { // 一样,重新起一组,说明d[0], 最小都 是=v了,想接在某个序列上是不可能了,只能是另起一段
                heap.Push(h, top)
                heap.Push(h, [2]int{v, 1})
                break
            } else if top[0]<v-1 { // 这一段已经无法接上了,要判断是不是超过3了
                if top[1]<3 {return false}
            } else { // top[0] == v-1 top[1]++, 以v结尾,并长度+1
                top[0]++
                top[1]++
                heap.Push(h, top)
                break
            }
        }
		
		if h.Len() == 0 {
			heap.Push(h, [2]int{v, 1})
			continue
		}
		
	}
	
	// 判断最终在堆里的序列长度是不是都超过
	for h.Len()>0 {
		top := heap.Pop(h).([2]int)
		if top[1]<3{return false}
	}
	
	return true
}

练习4 求第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 ≤ 数组的长度。

题目解析

构造一个小顶堆,容量是k, 遍历数组维护堆,始终保持堆内存储的是前k个最大值。

AC代码

type myHeap []int

func (h *myHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j] // 小顶堆
}

func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
	return len(*h)
}

func (h *myHeap) Pop() (v interface{}) {
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}

func (h *myHeap) Push(v interface{}) {
	*h = append(*h, v.(int))
}

func findKthLargest(nums []int, k int) int {
	 h:= &myHeap{} // 堆中始终保持前k个最大
	 heap.Init(h)

	 for _, v:= range nums {
		 if h.Len()<k { // 不够k个直接加
		 	heap.Push(h, v)
		 } else if (*h)[0]<v { // 如果当前第k大小于v, 就替换掉
			heap.Pop(h)
			heap.Push(h, v)
		}
	 }
	 
	return heap.Pop(h).(int) // 堆顶既是第k大值
}

七、总结

主要内容:

  1. 堆是一种完全二叉树数据结构,可以使用数组表示。其性质是二叉对中的每个子树,根的值总是要比孩子的值要大(大顶堆)。
  2. 作用:1)堆排序;2) 快速选择最优值(最小,最大,条件最优等)3)取集合中前K大元素;4)通过定义多维条件,快速选择出最优解。

笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目(首先AK F.*ing leetcode),给大家准备了一些题目,供大家练习参考。干他F.*ing (Fighting?)。

八、实战训练

代码基础训练题

光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那4题A了。

  1. 排序应用 力扣
  2. 利用小顶堆解丑数:力扣
  3. 利用条件构造解决复杂问题:力扣
  4. 求第K大值: 力扣

AK leetcode

leetcode相关题目都在下面了,拿起武器挨个点名呗。

力扣 堆相关题目


做完以上还觉得不过瘾,我给大家还准备了一些。

大神进阶

也可以去vjudge Problems - Virtual Judge 搜索相关题号

poj

http://poj.org/problem?id=1442

以下将序号替换就是题目链接。

  1. 1442 -- Black Box
  2. 3614 -- Sunscreen
  3. 2387 -- Til the Cows Come Home
  4. 3253 -- Fence Repair
  5. 2010 -- Moo University - Financial Aid
  6. 2312 -- Battle City
  7. 2431 -- Expedition

hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1242

以下将序号替换就是题目链接。

  1. Problem - 1242
  2. Problem - 4006
  3. Problem - 1873
  4. Problem - 1896
  5. Problem - 4546
  6. Problem - 1509

本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。