案例4-1.4 堆中的路径 + 基础实验4-2.5 关于堆的判断

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法
　
如果大家觉得有帮助的话，感谢大家帮忙点赞！收藏！转发！

堆的理解

首先，我们先看一下堆（优先级队列的模板），理解一下堆的存储

public class TestHeap {

    public int[] elem;
    public int usedSize;//当前堆当中的有效的元素的数据个数

    public TestHeap() {
        this.elem = new int[10];
        this.usedSize = 0;
    }

    public void initArray(int[] array) {
        elem = Arrays.copyOf(array,array.length);
        usedSize = elem.length;
    }

    /**
     * 建堆:【大根堆】
     * 时间复杂度：O(n)
     */

    public void createHeap() {
        for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 实现 向下调整
     * @param parent 每棵子树的根节点的下标
     * @param len 每棵子树的结束位置
     */

    private void shiftDown(int parent ,int len) {
        int child = 2 * parent + 1;
        //最起码是有左孩子
        while (child < len) {
            //判断 左孩子 和 右孩子  谁最大,前提是  必须有  右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;//此时 保存了最大值的下标
            }
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 入队
     * @param x
     */
    public void offer(int x) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        this.elem[usedSize] = x;
        usedSize++;
        shiftUp(usedSize-1);
    }

    private void shiftUp(int child) {
        int parent = (child-1) / 2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child-1) / 2;
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 出队
     */
    public int poll() {
        if(isEmpty()) {
            return -1;
        }
        int old = elem[0];
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    public void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

补充：

1. 堆是由数组存储，parent = 2 * child + 1 || parent = 2 * child + 2
2. 堆只保证最大值和最小值得存储，根节点的左右节点的大小不一定，有可能左孩子节点大于右孩子节点，有可能右孩子节点大于左孩子节点

例题 案例4-1.4 堆中的路径

思路：

1. 该堆是一个一个节点建立起来的，并不是先用所有节点建立一个树，然后再建立大根堆
   正确示例：
   
   错误示例：
   

#include
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
 
const ll maxx = 1e18;
const int N = 1e6+100;
const int p = 1e4+10;
const double eps = 1e-8;

int a[p];

int n,m,q;

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		
		int k=i;
		
		while(k>1&&a[k]<a[k/2])
		{
			swap(a[k],a[k/2]);
			k/=2;
		}
	}//输入数据，模拟建堆
	
	
	for(int i=1;i<=m;i++)
	{
		cin>>q;
		
		while(1)
		{
			if(q!=1)
				cout<<a[q]<<" ";
			else
				cout<<a[q]<<endl;
			
			q/=2;//根据堆中父子节点关系，输出路径
			
			if(q==0) break;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

补充：插入一个节点后，往上比较，要比较到根节点

	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		
		int k=i;
//插入一个节点后，往上比较，要比较到根节点
		while(k>1&&a[k]<a[k/2])
		{
			swap(a[k],a[k/2]);
			k/=2;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12

基础实验4-2.5 关于堆的判断

#include
#include
#include
#include
#include
struct Heap {
	int size;
	int item[1001];
}H;
void Insert(int temp) {
	H.size++;
	int i;
	for (i = H.size; i != 1 && H.item[i / 2] > temp; i /= 2)
		H.item[i] = H.item[i/2];
	H.item[i] = temp;
}
int find_pos(int temp) {
	int i;
	for (i = 1; i <= H.size; i++)
		if (H.item[i] == temp)
			return i;
}
bool isfather(int f, int s) {
	f = find_pos(f);
	s = find_pos(s);
	return (s / 2) == f;
}
bool isbro(int t1, int t2) {
	t1 = find_pos(t1);
	t2 = find_pos(t2);
	return (t1/2)==(t2/2);
}
bool isroot(int temp) {
	return H.item[1] == temp;
}
bool judge() {
	char a[1000],a1[1000],a2[1000];
	char rubbish[1000];//多余数组用来清空缓冲区
	int num1, num2;
	char c[100];
	bool f1=false;
	scanf("%d", &num1);
	scanf("%s",a);
	if (a[0] == 'i') {
		scanf("%s", a1);
		if (a1[0] == 'a') {
			scanf("%s", rubbish);
			scanf("%s", rubbish);
			scanf("%d", &num2);
				if (isfather(num2, num1))
					f1 = true;
		}
		else {
			scanf("%s", a2);
			if (a2[0] == 'r') {
				if (isroot(num1))
					f1 = true;
			}
			else {
				scanf("%s", rubbish);
				scanf("%d", &num2);
				if (isfather(num1, num2))
					f1 = true;
			}
		}
	}
	else {
		scanf("%d", &num2);
		if (isbro(num1, num2))
			f1 = true;
		fgets(rubbish, 1000, stdin);
	}
	return f1;
}
int main() {
	int N, M;
	char a[1000];
	scanf("%d%d", &N, &M);
	int item;
	for (int i = 0; i < N; i++) {
		scanf("%d", &item);
		Insert(item);
	}
	for (int i = 0; i < M; i++) {
		if (judge())
			printf("T\n");
		else
			printf("F\n");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90