个人网站用什么服务器,展示型的网站用,交互效果好的移动端网站,有哪些做特卖的网站一#xff1a;堆
1.1 堆的基本概念
堆分为两种#xff1a;大堆和小堆。它们之间的区别在于元素在堆中的排列顺序和访问方式。
大堆#xff08;Max Heap#xff09;#xff1a; 在大堆中#xff0c;父节点的值比它的子节点的值要大。也就是说#xff0c;堆的根节点是堆…一堆
1.1 堆的基本概念
堆分为两种大堆和小堆。它们之间的区别在于元素在堆中的排列顺序和访问方式。
大堆Max Heap 在大堆中父节点的值比它的子节点的值要大。也就是说堆的根节点是堆中最大的元素。大堆被用于实现优先级队列其中根节点的元素始终是队列中最大的元素。大堆可以通过以下特点来进行维护
对于每个父节点它的值大于或等于其子节点的值。
小堆Min Heap 在小堆中父节点的值比它的子节点的值要小。也就是说堆的根节点是堆中最小的元素。小堆常用于实现优先级队列其中根节点的元素始终是队列中最小的元素。小堆可以通过以下特点来进行维护
对于每个父节点它的值小于或等于其子节点的值。
以下是一个示例图示展示了一个包含7个元素的大堆和小堆的结构
大堆90/ \75 30/ \ / \20 15 10 7小堆7/ \10 30/ \ / \20 15 75 90这些图示说明了大堆和小堆的不同排列顺序。在大堆中父节点的值大于子节点的值而在小堆中父节点的值小于子节点的值。
注意堆总是一颗完全二叉树
1.2堆的存储方式
从堆的概念可知堆是一棵完全二叉树因此可以层序的规则采用顺序的方式来高效存储 注意对于非完全二叉树则不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。
将元素存储到数组中后可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标则有
如果i为0则i表示的节点为根节点如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子
1.3 堆的下沉
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据如果将其创建成小堆呢
仔细观察上图后发现根节点的左右子树已经完全满足堆的性质因此只需将根节点向下调整好即可。
下面是代码实现
// shiftDown方法用来实现下沉操作
// array参数是待构建小堆的数组
// parent参数是当前需要下沉的节点的索引
public void shiftDown(int[] array, int parent) {int length array.length;int child 2 * parent 1; // 左子节点索引while (child length) {// 找到左右孩子中较小的孩子if (child 1 length array[child] array[child 1]) {child; // 如果右子节点存在并且小于左子节点的值则将child指向右子节点}// 如果当前节点小于或等于左右子节点中较小的节点说明已经符合小堆要求if (array[parent] array[child]) {break;}// 否则交换当前节点和较小子节点的值接着需要继续向下调整int temp array[parent];array[parent] array[child];array[child] temp;parent child;child 2 * parent 1;}
}
这段代码实现了堆排序中的下沉操作也称为向下调整或堆化。下沉操作用于维护小堆的性质确保父节点永远小于或等于其子节点。
时间复杂度分析 最坏的情况即图示的情况从根一路比较到叶子比较的次数为完全二叉树的高度即时间复杂度为Olog n 1.4 堆的创建
那对于普通的序列{ 1,5,3,8,7,6 }即根节点的左右子树不满足堆的特性又该如何调整呢 参考代码
public static void createHeap(int[] array) {// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整int root ((array.length-2)1);for (; root 0; root--) {shiftDown(array, root);}
}1.5建堆的时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 因此建堆的时间复杂度为O(N)。
1.6堆的插入和删除
1.6.1 堆的插入
堆的插入总共需要两个步骤
先将元素放入到底层空间中(注意空间不够时需要扩容)将最后新插入的节点向上调整直到满足堆的性质 下面是堆的删除操作的代码实现包含详细注释
public void shiftUp(int child) {// 找到child的双亲int parent (child - 1) / 2;while (child 0) {// 如果双亲比孩子大parent满足堆的性质调整结束if (array[parent] array[child]) {break;}else{// 将双亲与孩子节点进行交换int t array[parent];array[parent] array[child];array[child] t;// 小的元素向下移动可能到值子树不满足对的性质因此需要继续向上调增child parent;parent (child - 1) / 1;}}
}1.6.2 堆的删除
注意堆的删除一定删除的是堆顶元素。具体如下
将堆顶元素对堆中最后一个元素交换将堆中有效数据个数减少一个对堆顶元素进行向下调整 下面是堆的删除操作的代码实现包含详细注释
public void deleteTop() {// 将堆顶元素与堆中最后一个元素交换array[0] array[size - 1];// 堆中有效数据个数减少一个size--;// 对堆顶元素进行向下调整int parent 0; // 当前节点的索引// 持续向下调整直到满足堆的性质while (true) {// 左孩子节点的索引int leftChild parent * 2 1;// 右孩子节点的索引int rightChild leftChild 1;// 父节点与左右孩子节点中值最大的节点进行交换int maxChild parent; // 最大值节点的索引// 如果左孩子存在且大于父节点则更新最大值节点if (leftChild size array[leftChild] array[maxChild]) {maxChild leftChild;}// 如果右孩子存在且大于当前最大值节点则更新最大值节点if (rightChild size array[rightChild] array[maxChild]) {maxChild rightChild;}// 如果最大值节点是当前节点本身则调整结束 if (maxChild parent) {break;} else {// 交换最大节点与父节点int temp array[parent];array[parent] array[maxChild];array[maxChild] temp;// 更新当前节点为最大值节点parent maxChild;}}
}二优先级队列
2.1 概念
前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队列时可能需要优先级高的元素先出队列该中场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话初中那会班主任排座位时可能会让成绩好的同学先挑座位。
在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
2.2堆的使用
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的本文主要介绍PriorityQueue。 关于PriorityQueue的使用要注意
使用时必须导入PriorityQueue所在的包即PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException异常不能插入null对象否则会抛出NullPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
PriorityQueue中常见的构造方法
构造器功能介绍PriorityQueue()创建一个空的优先级队列默认容量是11PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意 initialCapacity不能小于1否则会抛IllegalArgumentException异 常PriorityQueue(Collection? extends E c)用一个集合来创建优先级队列
下面是使用示例
static void TestPriorityQueue(){// 创建一个空的优先级队列底层默认容量是11PriorityQueueInteger q1 new PriorityQueue();// 创建一个空的优先级队列底层的容量为initialCapacityPriorityQueueInteger q2 new PriorityQueue(100);ArrayListInteger list new ArrayList();list.add(4);list.add(3);list.add(2);list.add(1);// 用ArrayList对象来构造一个优先级队列的对象// q3中已经包含了三个元素PriorityQueueInteger q3 new PriorityQueue(list);System.out.println(q3.size());System.out.println(q3.peek());}注意默认情况下PriorityQueue队列是小堆如果需要大堆需要用户提供比较器
// 用户自己定义的比较器直接实现Comparator接口然后重写该接口中的compare方法即可
class IntCmp implements ComparatorInteger{Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}
public class TestPriorityQueue {public static void main(String[] args) {PriorityQueueInteger p new PriorityQueue(new IntCmp());p.offer(4);p.offer(3);p.offer(2);p.offer(1);p.offer(5);System.out.println(p.peek());}
}下面是 PriorityQueue中常用的方法
函数名功能介绍booleanoffer(E e)插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度 注意空间不够时候会进行扩容E peek()获取优先级最高的元素如果优先级队列为空返回nullE poll()移除优先级最高的元素并返回如果优先级队列为空返回nullint size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空空返回true
下面是这些方法的使用示例
import java.util.PriorityQueue;public class Main {public static void main(String[] args) {PriorityQueueInteger heap new PriorityQueue();// 测试插入元素heap.offer(10); // 返回 trueheap.offer(5); // 返回 trueheap.offer(15); // 返回 trueheap.offer(2); // 返回 true// 测试获取优先级最高的元素// 结果为 2System.out.println(heap.peek());// 测试移除优先级最高的元素// 结果为 2System.out.println(heap.poll());// 测试获取有效元素的个数// 结果为 3System.out.println(heap.size());// 测试清空优先级队列heap.clear();// 测试检测优先级队列是否为空// 结果为 trueSystem.out.println(heap.isEmpty());}
}
以下是JDK 1.8中PriorityQueue的扩容方式
优先级队列的扩容说明
如果容量小于64时是按照oldCapacity的2倍方式扩容的如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容
MAX_ARRAY_SIZE等于Integer.MAX_VALUE - 8Integer.MAX_VALUE - 8。等于 2,147,483,639。
2.3 用堆模拟实现优先级队列
我们通过堆可以模拟实现优先级队列因为堆具有以下特性
大堆或小堆堆可以是大堆或小堆其中大堆意味着父节点的值大于或等于其子节点的值而小堆意味着父节点的值小于或等于其子节点的值。优先级定义我们可以将堆中的元素与优先级相关联。较高的优先级可以根据堆类型来确定是最大值还是最小值。
优先性在优先级队列中体现在以下方面
插入元素由于堆的性质插入的元素会按照其优先级找到正确的位置插入。较高优先级的元素会被放置在堆的顶部根节点。删除元素从堆中删除元素时会删除具有最高最大堆或最低最小堆优先级的元素。这样每次删除的元素都是具有最高/最低优先级的元素。
通过以上方式可以使用堆来实现优先级队列确保具有更高优先级的元素优先被处理或删除。
下面我们基于堆来模拟实现一个优先级队列
public class MyPriorityQueue {// 演示作用不再考虑扩容部分的代码private int[] array new int[100]; // 使用数组来存储元素private int size 0; // 当前队列的大小// 向优先队列中插入元素public void offer(int e) {array[size] e; // 将元素插入数组末尾shiftUp(size - 1); // 对插入的元素进行上浮操作以保持堆的性质}// 弹出并返回优先队列中最高优先级的元素public int poll() {int oldValue array[0]; // 保存堆顶元素的值array[0] array[--size]; // 将堆尾元素移到堆顶shiftDown(0); // 对堆顶元素进行下沉操作以保持堆的性质return oldValue; // 返回弹出的元素值}// 返回优先队列中最高优先级的元素public int peek() {return array[0]; // 直接返回堆顶元素的值}
}请注意此处的代码仅展示了演示目的没有考虑扩容部分的代码实现。
三 堆的应用
3.1PriorityQueue的实现
用堆作为底层结构封装优先级队列这点我们已经讲过在此不过多赘述
3.2堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
建堆 升序建大堆 降序建小堆利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 3.3Top-k问题
TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 我们可以通过使用堆来解决TOP-K问题具体步骤如下
一 创建一个大小为K的最小堆或最大堆取决于你是求前K个最小值还是最大值。 二遍历数据集合对于每个元素执行以下操作
如果堆的大小小于K将当前元素插入堆中。如果堆的大小等于K比较当前元素与堆顶元素的大小如果当前元素大于堆顶元素最小堆将堆顶元素弹出将当前元素插入堆中。如果当前元素小于堆顶元素最大堆跳过当前元素。
三 遍历完数据集合后堆中的元素即为前K个最小或最大的元素。
下面是一个使用Java实现堆解决TOP-K问题的示例代码
import java.util.PriorityQueue;public class TopK {public static void main(String[] args) {int[] nums {9, 3, 7, 5, 1, 8, 2, 6, 4};int k 4;findTopK(nums, k);}private static void findTopK(int[] nums, int k) {PriorityQueueInteger minHeap new PriorityQueue();for (int num : nums) {if (minHeap.size() k) {minHeap.offer(num);} else if (num minHeap.peek()) {minHeap.poll();minHeap.offer(num);}}System.out.println(Top k elements:);while (!minHeap.isEmpty()) {System.out.print(minHeap.poll() );}}
}以上示例中对数组nums求前4个最小元素使用了PriorityQueue实现了一个小顶堆。遍历数组时根据堆的大小和当前元素与堆顶元素的比较进行插入和调整。最后打印出堆中的元素即为前4个最小的元素。
四java对象的比较
4.1PriorityQueue中插入对象
优先级队列在插入元素时有个要求插入的元素不能是null或者元素之间必须要能够进行比较为了简单起见我们只是插入了Integer类型那优先级队列中能否插入自定义类型对象呢
class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank rank;this.suit suit;}
}
public class TestPriorityQueue {public static void TestPriorityQueue(){PriorityQueueCard p new PriorityQueue();p.offer(new Card(1, ♠));p.offer(new Card(2, ♠));}public static void main(String[] args) {TestPriorityQueue();}
}优先级队列底层使用堆而向堆中插入元素时为了满足堆的性质必须要进行元素的比较而此时Card是没有办法直接进行比较的因此抛出异常。 4.2 元素的比较
4.2.1基本元素的比较
在Java中基本类型的对象可以直接比较大小。
public class TestCompare {public static void main(String[] args) {int a 10;int b 20;System.out.println(a b);System.out.println(a b);System.out.println(a b);char c1 A;char c2 B;System.out.println(c1 c2);System.out.println(c1 c2);System.out.println(c1 c2);boolean b1 true;boolean b2 false;System.out.println(b1 b2);System.out.println(b1 ! b2);}
}4.2.2 对象比较的问题
4.2.2.1equals
class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank rank;this.suit suit;}
}
public class TestPriorityQueue {public static void main(String[] args) {Card c1 new Card(1, ♠);Card c2 new Card(2, ♠);Card c3 c1;//System.out.println(c1 c2); // 编译报错System.out.println(c1 c2); // 编译成功 ---- 打印false因为c1和c2指向的是不同对象//System.out.println(c1 c2); // 编译报错System.out.println(c1 c3); // 编译成功 ---- 打印true因为c1和c3指向的是同一个对象}
}c1、c2和c3分别是Card类型的引用变量上述代码在比较编译时
c1 c2 编译失败c1 c2 编译成功c1 c2 编译失败
从编译结果可以看出Java中引用类型的变量不能直接按照 或者 方式进行比较。 那为什么 可以比较
因为对于用户实现自定义类型都默认继承自Object类而Object类中提供了equal方法而默认情况下调用的就是equal方法但是该方法的比较规则是没有比较引用变量引用对象的内容而是直接比较引用变量的地址但有些情况下该种比较就不符合题意。
// Object中equal的实现可以看到直接比较的是两个引用变量的地址
public boolean equals(Object obj) {return (this obj);
}有些情况下需要比较的是对象中的内容比如向优先级队列中插入某个对象时需要对按照对象中内容来调整堆那该如何处理呢答案是重写覆盖基类的equals
public class Card {public int rank; // 数值public String suit; // 花色public Card(int rank, String suit) {this.rank rank;this.suit suit;}Overridepublic boolean equals(Object o) {// 自己和自己比较if (this o) {return true;}// o如果是null对象或者o不是Card的子类if (o null || !(o instanceof Card)) {return false;}// 注意基本类型可以直接比较但引用类型最好调用其equal方法Card c (Card)o;return rank c.rank suit.equals(c.suit);}
}注意 一般覆写 equals 的套路就是上面演示的
如果指向同一个对象返回 true如果传入的为 null返回 false如果传入的对象类型不是 Card返回 false按照类的实现目标完成比较例如这里只要花色和数值一样就认为是相同的牌注意下调用其他引用类型的比较也需要 equals例如这里的 suit 的比较
覆写基类equal的方式虽然可以比较但缺陷是equal只能按照相等进行比较不能按照大于、小于的方式进行比较。
4.2.2.2 Comparble接口
Comparble是JDK提供的泛型的比较接口类源码实现具体如下
public interface ComparableE {// 返回值:// 0: 表示 this 指向的对象小于 o 指向的对象// 0: 表示 this 指向的对象等于 o 指向的对象// 0: 表示 this 指向的对象大于 o 指向的对象int compareTo(E o);
}对用用户自定义类型如果要想按照大小与方式进行比较时在定义类时实现Comparble接口即可然后在类中重写compareTo方法。
Java中的Comparable接口是用于实现对象的自然排序的接口。它包含一个compareTo方法用于比较两个对象的顺序。
compareTo方法有以下三种返回值
如果当前对象小于被比较对象则返回一个负整数。如果当前对象等于被比较对象则返回0。如果当前对象大于被比较对象则返回一个正整数。
下面是一个简单的例子演示如何使用Comparable接口来自然排序自定义的Person类
import java.util.ArrayList;
import java.util.Collections;class Person implements ComparablePerson {private String name;private int age;public Person(String name, int age) {this.name name;this.age age;}// 实现compareTo方法Overridepublic int compareTo(Person other) {return this.age - other.age; // 按照年龄排序}// 其他getter和setter方法Overridepublic String toString() {return Person{ name name \ , age age };}
}public class Main {public static void main(String[] args) {ArrayListPerson people new ArrayList();people.add(new Person(Alice, 25));people.add(new Person(Bob, 20));people.add(new Person(Charlie, 30));System.out.println(排序前:);for (Person person : people) {System.out.println(person);}Collections.sort(people); // 使用Collections.sort()方法进行排序时会自动调用compareTo()方法进行比较System.out.println(排序后:);for (Person person : people) {System.out.println(person);}}
}输出结果
排序前:
Person{nameAlice, age25}
Person{nameBob, age20}
Person{nameCharlie, age30}
排序后:
Person{nameBob, age20}
Person{nameAlice, age25}
Person{nameCharlie, age30}在上面的代码中我们定义了一个Person类并实现了Comparable接口。我们通过compareTo方法比较了两个Person对象的年龄并在Main类中使用Collections.sort方法对people列表进行了排序。排序后列表中的Person对象按照年龄的升序排列。
注意Compareble是java.lang中的接口类可以直接使用。
4.2.2.3 基于比较器比较
在Java中如果我们想要比较两个对象并根据它们的属性值进行排序或判断它们的相对顺序我们可以使用比较器Comparator进行操作。
比较器是一个用于定义对象之间比较行为的接口。它包含了一个用于比较两个对象的方法 - compare()。该方法接受两个参数分别是要比较的两个对象然后返回一个整数值来表示它们的相对顺序。
下面是一个简单的示例展示如何使用比较器比较两个Person对象
import java.util.*;// 定义Person类
class Person {private String name;private int age;public Person(String name, int age) {this.name name;this.age age;}// 省略其他属性和方法public String getName() {return name;}public int getAge() {return age;}
}// 定义比较器类
class AgeComparator implements ComparatorPerson {Overridepublic int compare(Person person1, Person person2) {if (person1.getAge() person2.getAge()) {return -1; // person1在前} else if (person1.getAge() person2.getAge()) {return 1; // person2在前} else {return 0; // 保持顺序不变}}
}public class Main {public static void main(String[] args) {// 创建Person对象Person person1 new Person(Alice, 25);Person person2 new Person(Bob, 30);Person person3 new Person(John, 20);// 创建比较器对象AgeComparator comparator new AgeComparator();// 使用比较器比较对象int result1 comparator.compare(person1, person2); // 返回-1person1在前int result2 comparator.compare(person2, person1); // 返回1person2在前int result3 comparator.compare(person1, person3); // 返回0保持顺序不变System.out.println(result1);//-1System.out.println(result2);//1System.out.println(result3);//0}
}在上述代码中我们定义了一个Person类其中包含了姓名name和年龄age属性。然后我们创建了一个比较器类AgeComparator实现了Comparator接口并重写了compare()方法来根据年龄来判断相对顺序。
在main()方法中我们创建了三个Person对象并使用AgeComparator比较器对象来比较它们的年龄。最后我们打印了比较的结果验证了对象之间的比较行为。
这就是基于比较器比较两个对象的示例。通过实现Comparator接口并重写compare()方法我们可以定制化对象之间的比较行为从而实现根据特定属性进行排序或判断相对顺序。
注意Comparator是java.util 包中的泛型接口类使用时必须导入对应的包。
我们要注意区分Comparable和Comparato
实现Comparable接口重写compareTo方法实现Comparator接口重写compare方法
三种比较方式对比
覆写的方法说明Object.equals因为所有类都是继承自 Object 的所以直接覆写即可不过只能比较相等与否Comparable.compareTo需要手动实现接口侵入性比较强但一旦实现每次用该类都有顺序属于内部顺序Compareble是java.lang中的接口类可以直接使用。Comparator.compare需要实现一个比较器对象对待比较类的侵入性弱但对算法代码实现侵入性强 Comparator是java.util 包中的泛型接口类使用时必须导入对应的包。
