数据结构-非线性结构-树形结构:有序树 ->二叉树 -> 平衡二叉树(任何节点的左右子树的高度差不大于1)-> 完全二叉树(除最底层外的其他层都被填满,且最底层左到右填入) -> 堆(优先队列)

本文主要是介绍数据结构-非线性结构-树形结构:有序树 ->二叉树 -> 平衡二叉树(任何节点的左右子树的高度差不大于1)-> 完全二叉树(除最底层外的其他层都被填满,且最底层左到右填入) -> 堆(优先队列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

完全二叉树:即除了最底层,其他层的节点都被元素填满,且最底层左到右填入。

完全二叉树属于平衡二叉树。

堆是一种完全二叉树,且满足以下条件:

  • 最大堆:每个节点都比其子树所有节点大的完全二叉树;
  • 最小堆:每个节点都比其子树所有节点小的完全二叉树;

在这里插入图片描述
我们对堆中的结点按层进行编号,可以将堆逻辑结构映射到数组中

  • 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
  • 小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

在这里插入图片描述

一、二叉堆(Binary Heap)

add、extractMax操作的时间复杂度都是 O ( l o g n ) O(logn) O(logn)

在这里插入图片描述
由上图可知,二叉堆可以用动态数组来实现。
在这里插入图片描述

在这里插入图片描述

MyArray.java

/*** 数组** @author* @version 2018/8/4*/
public class MyArray<E> {private E[] arr;private int size;public MyArray(int capacity){arr = (E[])new Object[capacity];size = 0;}public MyArray() {this(10);}public MyArray(E[] data){arr = (E[])new Object[data.length];for(int i = 0; i <arr.length; i++){arr[i] = data[i];}size = data.length;}public int getSize(){return size;}public int getCapacity(){return arr.length;}public boolean isEmpty(){return size == 0;}/*** 向数组头部插入一个元素** @param e* @return void* @author whx* @version 2018/8/4*/public void addFirst(E e){add(0,e);}/*** 向数组尾部插入一个元素** @param e* @return void* @author whx* @version 2018/8/4*/public void addLast(E e){add(size,e);}/*** 向数组指定位置插入一个元素** @param index* @param e* @return void* @author whx* @version 2018/8/4*/public void add(int index, E e){if(index < 0 || index > size){throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}if(size == arr.length){
//			throw new IllegalArgumentException("Add failed. Array is full.");//数组动态扩容两倍resize(2*arr.length);}for (int i= size-1; i >= index; i--){arr[i+1] = arr[i];}arr[index] = e;size++;}private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newData[i] = arr[i];}arr = newData;}/*** 获取指定位置的元素** @param index* @return E* @author whx* @version 2018/8/4*/public E get(int index){if(index < 0 || index >= size){throw new IllegalArgumentException("Get failed. index is Illegal.");}return arr[index];}/*** 获取第一个元素** @param* @return E* @author whx* @version 2018/8/4*/public E getFirst() {return arr[0];}/*** 获取最后一个元素** @param* @return E* @author whx* @version 2018/8/4*/public E getLast() {return get(size - 1);}/*** 修改指定位置的元素** @param index* @param e* @return void* @author whx* @version 2018/8/4*/public void set(int index, E e){if (index < 0 || index >= size){throw new IllegalArgumentException("Set failed. index is Illegal.");}arr[index] = e;}/*** 查看数组中是否包含某个元素** @param e* @return boolean* @author whx* @version 2018/8/4*/public boolean contains(E e){for (int i = 0; i < size; i++) {if(arr[i].equals(e)){return true;}}return false;}/*** 查找元素在数组中的位置** @param e* @return int* @author whx* @version 2018/8/4*/public int indexOf(E e){for (int i = 0; i < size; i++) {if(arr[i].equals(e)){return i;}}return -1;}/*** 移除数组中的一个元素** @param index* @return int* @author whx* @version 2018/8/4*/public E remove(int index){if (index < 0 || index >= size){throw new IllegalArgumentException("Remove failed. index is Illegal.");}E result = arr[index];for (int i = index + 1; i < size; i++) {arr[i-1] = arr[i];}size--;//修改对象引用,垃圾回收机制回收arr[size] = null;//动态缩小数组一半容量if(size == arr.length/4 && arr.length/2 != 0){resize(arr.length/2);}return result;}/*** 移除数组中的第一个元素** @param* @return E* @author whx* @version 2018/8/4*/public E removeFirst(){return remove(0);}/*** 移除数组中的最后一个元素** @param* @return int* @author whx* @version 2018/8/4*/public E removeLast(){return remove(size - 1);}/*** 移除数组中的某个元素** @param e* @return void* @author whx* @version 2018/8/4*/public void removeElement(E e){int index = indexOf(e);if(index != -1){remove(index);}}/*** 将索引为i和j的两个元素互相交换** @param i* @param j* @return void* @author whx* @version 2018/8/19*/public void swap(int i, int j){if (i < 0 || i >= size || j < 0 || j >= size){throw new IllegalArgumentException("Swap failed. index is Illegal.");}E temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*** 自定义toString方法** @param* @return java.lang.String* @author whx* @version 2018/8/4*/@Overridepublic String toString(){StringBuilder result = new StringBuilder();result.append(String.format("Array: size = %d , capacity = %d\n",size,arr.length));result.append("[");for (int i = 0; i < size; i++){result.append(arr[i]);if(i != size - 1){result.append(", ");}}result.append("]");return result.toString();}}

1、最大堆

在这里插入图片描述

MaxHeap.java

/*** 最大堆* 完全二叉树实现、树中的根结点都表示树中的最大元素结点** @author whx* @version 2018/8/19*/
public class MaxHeap<E extends Comparable<E>> {private MyArray<E> arr;public MaxHeap(int capacity) {arr = new MyArray<>(capacity);}public MaxHeap() {arr = new MyArray<>();}// heapify:将任意数组整理成堆的形状public MaxHeap(E[] data) {arr = new MyArray<>(data);for (int i = parent(data.length - 1); i >= 0; i--){siftDown(i);}}// 返回堆中的元素个数public int size() {return arr.getSize();}public boolean isEmpty() {return arr.isEmpty();}/*** 查找用数组实现的完全二叉树中该索引下节点的父亲节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int parent(int index) {if (index == 0) {throw new IllegalArgumentException("root doesn't have parent.");}return (index - 1) / 2;}/*** 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int leftChild(int index) {return (index * 2) + 1;}/*** 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int rightChild(int index) {return (index * 2) + 2;}/*** 向最大堆中添加元素** @param e* @return void* @author whx* @version 2018/8/19*/public void add(E e) {arr.addLast(e);shifUp(arr.getSize() - 1);}/*** 上浮节点** @param k* @return void* @author whx* @version 2018/8/19*/private void shifUp(int k) {while (k > 0 && arr.get(parent(k)).compareTo(arr.get(k)) < 0) {arr.swap(k, parent(k));k = parent(k);}}/*** 查找堆中最大值** @param* @return E* @author whx* @version 2018/8/19*/public E findMax() {if (arr.getSize() == 0) {throw new IllegalArgumentException("FindMax failed. heap is empty.");}return arr.get(0);}/*** 取出最大值** @param* @return E* @author whx* @version 2018/8/20*/public E extractMax() {E result = findMax();arr.swap(0, arr.getSize() - 1);arr.removeLast();siftDown(0);return result;}/*** 下沉节点** @param k* @return void* @author whx* @version 2018/8/25*/private void siftDown(int k) {while (k >= 0 && leftChild(k) < arr.getSize()) {int j = leftChild(k);//找到k节点的左右子节点的最大值jif (j + 1 < arr.getSize() && arr.get(j + 1).compareTo(arr.get(j)) > 0) {j = rightChild(k);}// 运行到此,arr[j] 是 leftChild 和 rightChild 中的最大值//比较大小判断是否还需要下沉操作if (arr.get(k).compareTo(arr.get(j)) > 0) {break;}arr.swap(k, j);k = j;}}// 取出堆中的最大元素,并且替换成元素elempublic E replace(E elem) {E ret = findMax();arr.set(0, elem);siftDown(0);return ret;}}

2、最小堆

MinHeap.java

/*** 最小堆* 完全二叉树实现、树中的根结点都表示树中的最小元素结点** @author whx* @version 2018/8/25*/
public class MinHeap<E extends Comparable<E>> {private MyArray<E> arr;public MinHeap(int capacity){arr = new MyArray<>(capacity);}public MinHeap() {arr = new MyArray<>();}public int size(){return arr.getSize();}public boolean isEmpty(){return arr.isEmpty();}/*** 查找用数组实现的完全二叉树中该索引下节点的父亲节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int parent(int index){if(index == 0){throw new IllegalArgumentException("root doesn't have parent.");}return (index - 1) / 2;}/*** 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int leftChild(int index){return (index * 2) + 1;}/*** 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int rightChild(int index){return (index * 2) + 2;}/*** 向最大堆中添加元素** @param e* @return void* @author whx* @version 2018/8/19*/public void add(E e){arr.addLast(e);shifUp(arr.getSize() - 1);}/*** 上浮节点** @param k* @return void* @author whx* @version 2018/8/19*/private void shifUp(int k) {while (k > 0 && arr.get(parent(k)).compareTo(arr.get(k)) > 0){arr.swap(k,parent(k));k = parent(k);}}/*** 查找堆中最小值** @param* @return E* @author whx* @version 2018/8/19*/public E findMin(){if(arr .getSize() == 0){throw new IllegalArgumentException("FindMax failed. heap is empty.");}return arr.get(0);}/*** 取出最小值** @param* @return E* @author whx* @version 2018/8/20*/public E extractMin(){E result = findMin();arr.swap(0,arr.getSize() - 1);arr.removeLast();siftDown(0);return result;}/*** 下沉节点** @param k* @return void* @author whx* @version 2018/8/25*/private void siftDown(int k) {while (k >= 0 && leftChild(k) < arr.getSize()){int j = leftChild(k);//找到k节点的左右子节点的最大值jif (j + 1 < arr.getSize() && arr.get(j + 1).compareTo(arr.get(j)) < 0) {j = rightChild(k);}//比较大小判断是否还需要下沉操作if(arr.get(k).compareTo(arr.get(j)) < 0){break;}arr.swap(k,j);k = j;}}}

三、heapify:将任意数组整理成堆的形状

在这里插入图片描述
在这里插入图片描述

四、优先队列

在这里插入图片描述
Queue.java

/*** 队列** @author whx* @version 2018/8/4*/
public interface Queue<E> {/*** 获取队列的大小** @param* @return int* @author whx* @version 2018/8/4*/int getSize();/*** 查看队列是否为空** @param* @return boolean* @author whx* @version 2018/8/4*/boolean isEmpty();/*** 将一个元素插入队尾** @param e* @return void* @author whx* @version 2018/8/4*/void enqueue(E e);/*** 将队首一个元素移除队列** @param* @return E* @author whx* @version 2018/8/4*/E dequeue();/*** 获取队首的一个元素** @param* @return E* @author whx* @version 2018/8/4*/E getFront();
}

PriorityQueue.java

/*** 优先队列* 利用最大堆实现** @author whx* @version 2018/8/25*/
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {private MaxHeap<E> maxHeap;public PriorityQueue() {maxHeap = new MaxHeap<>();}@Overridepublic int getSize() {return maxHeap.size();}@Overridepublic boolean isEmpty() {return maxHeap.isEmpty();}@Overridepublic void enqueue(E e) {maxHeap.add(e);}@Overridepublic E dequeue() {return maxHeap.extractMax();}@Overridepublic E getFront() {return maxHeap.findMax();}
}

这篇关于数据结构-非线性结构-树形结构:有序树 ->二叉树 -> 平衡二叉树(任何节点的左右子树的高度差不大于1)-> 完全二叉树(除最底层外的其他层都被填满,且最底层左到右填入) -> 堆(优先队列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128841

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能