堆

1 前言在之前的文章里，我分享了Js版的堆实现和C语言版的堆实现, 了解的话，堆的实现其实并不难，以大顶堆为例，简略演绎就是插入时候，比节点小，就一直向下沉，让更大的上浮，直到最大的上浮到根节点。 1. 数据与构造与算法: 堆 C语言形容 2. 数据结构与算法: 堆 优先队列 JavaScript语言形容 优先队列基于堆实现，顾名思义是一个有优先级的队列，最高优先级的最先出列，低优先级最初出列（如果是最小堆则刚好相同）。明天咱们就用堆和优先队列高效解决一些问题，别离是经典的TopK问题-堆解法，以及3D接雨水-优先队列解法。 2 TopK问题-堆解法题目：215. 数组中的第K个最大元素 2.1 思路在之前的文章里，我分享了基于Partition和ThreePartition算法的原地排序，来高效求解TopK问题，原地排序，没有应用额定的空间，空间复杂度很低，然而工夫复杂度稳定比拟大，如果随机取的基准值很现实，那么效率超高，但如果数组里值散布很发散，随机取的基准值也很不现实，那么这种极其状况下，那么效率就不是很高,尽管《算法导论》证实了Partition算法是近似线性，但其线性常数项相对比1大多了； 而堆解法呢，就是稳固的工夫空间复杂度，建堆的最差复杂度是确定的，遍历一遍的复杂度只有O(N),能够确定在kLog(k) + O(N)。 2.2 C语言形容先建设一个容量为k的最小堆，后续的元素，只有比堆顶大的，才入堆，否则间接略过，最初堆顶元素就是第K大元素。 typedef struct MinHeap { int *data; //数据域 int size; //长度 int max;//最大长度} MinHeap;void insert(struct MinHeap *p, int item){ if (p->size == p->max) { printf("******:\n"); return; } int i = ++p->size; for (; p->data[i/2] > item; i/=2) { if (i <= 1) { break; } p->data[i] = p->data[i/2]; } p->data[i] = item;}void delete(struct MinHeap *p){ p->data[1] = p->data[p->size--]; int i = 1; int tmp; while(2*i <= p->size){ //如果有右节点 if (2*i + 1 <= p->size) { if (p->data[2*i + 1] < p->data[i] || p->data[2*i] < p->data[i]) { if (p->data[2*i + 1] < p->data[2*i]) { tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; } }else{ return; } }else{ //只有左节点 if (p->data[2*i] < p->data[i]) { tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; }else{ return; } } }}int findKthLargest(int* nums, int numsSize, int k){ struct MinHeap *heap; heap=(struct MinHeap *)malloc(sizeof(struct MinHeap)); if (heap == NULL) { printf("malloc error \n"); return 0; } heap->size = 0; heap->max = k + 1; heap->data = (int*)malloc(sizeof(int)*heap->max); if(heap->data == NULL) { printf("malloc error \n"); return 0; } heap->data[0] = 9999; for (int i = 0; i < numsSize; ++i) { if(i < k){ insert(heap, nums[i]); }else{ if(nums[i] > heap->data[1]){ delete(heap); insert(heap, nums[i]); } } } return heap->data[1];} ...

前言在学习ScheduledThreadPoolExecutor时，发现该线程池应用的队列为DelayedWorkQueue，DelayedWorkQueue是一个基于堆构造实现的延时队列和优先级队列，为了搞明确DelayedWorkQueue的实现，本篇文章先对堆数据结构进行学习，并且基于堆数据结构实现一个优先级队列以加深对堆数据结构的了解。 注释一. 堆的定义堆的定义如下所示。 堆是一颗齐全二叉树；父节点的元素如果总是大于等于子节点，称之为大根堆；父节点的元素如果总是小于等于子节点，称之为小根堆。要了解堆，首先须要理解什么是齐全二叉数。齐全二叉树定义为：如果二叉树的深度为h，那么除第h层外，其余第1到h-1层的节点数都达到最大值，第h层的所有节点都间断集中在右边。一颗齐全二叉树如下所示。 大根堆如下所示。 小根堆如下所示。 通常，堆中元素用一个数组来寄存。以上图的小根堆为例，节点旁边的数字代表以后节点在数组中的索引，能够发现其法则就是：依照层序遍历的形式遍历齐全二叉树，并每遍历一个节点就将以后节点的元素增加到数组中。所以上图的小根堆以数组示意如下。 最初，能够依据堆中某个节点在数组中的索引来计算这个节点的左右子节点和父节点在数组中的索引。计算的Java代码如下所示。 public class HeapTry { public int getLeft(int i) { return (i + 1) * 2 - 1; } public int getRigth(int i) { return (i + 1) * 2; } public int getParent(int i) { if (i == 0) { return 0; } return (i - 1) / 2; } ......}二. 堆的性质大根堆的性质：父节点的元素总是大于等于子节点。小根堆的性质：父节点的元素总是小于等于子节点。以小根堆为例，思考这样一个场景：给定一个小根堆，而后将根节点的元素删除并为根节点增加一个新的元素，新的元素不满足小于等于子节点的元素，此时小根堆的性质受到毁坏。图示如下。 对于上述场景，如果须要复原小根堆的性质，则以根节点作为第一个父节点，依照如下步骤执行。 将父节点与子节点的元素进行比拟并失去元素最小的节点，如果元素最小的节点是父节点，那么曾经复原小根堆的性质，执行完结；如果元素最小的节点是某个子节点，执行步骤2；将父节点与元素最小的子节点调换元素，因为调换元素后子节点有可能毁坏小根堆性质，因而从子节点开始，执行步骤1，直到复原小根堆性质。图示如下。 将复原小根堆性质的算法用Java代码实现如下。 ...

堆是一种常见的数据结构。其底层就是一个用数组实现的二叉树。然而没有父指针和子指针。 依据堆属性来进行排序。分为最小堆和最大堆。 最小堆：父节点的值比每个子节点的值都要小最大堆：父节点的值比每一个子节点的值都要大个别利用在以下场景： 疾速排序(取最大值 最小值)优先队列最大堆/最小堆spl中SplHeap抽象类实现了堆数据结构。SplMaxHeap和SplMinHeap继承自SplHeap，别离用来实现最大堆和最小堆。以下代码以最大堆为例做阐明，最小堆的时候和最大堆相似 // 最大堆$maxheap = new SplMaxHeap();// 插入节点并重建堆$maxheap->insert(12);$maxheap->insert(3);$maxheap->insert(222);$maxheap->insert(2);$maxheap->insert(312);$maxheap->insert(3);$maxheap->insert(13);$maxheap->insert(32);$maxheap->insert(3);$maxheap->insert(1);echo "最大推顶层元素：" . $maxheap->top() . PHP_EOL;// extract提取顶层元素// 取出节点并重建堆 echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "判断是否是空堆：" . PHP_EOL;var_dump($maxheap->isEmpty());// 当堆长度为0 的时候该堆为空堆echo "以后堆长度：" . $maxheap->count() . PHP_EOL;实现自定义推排序很多时候，单纯的数字大小比拟不能满足咱们对于堆数据结构的要求。比方咱们要基简单数组实现堆排序。SplHeap 类提供了compare形象办法，只有咱们实现本人的compare办法，就能够对任意数据类型进行最小堆最大堆排序 class MmaxHead extends SplHeap{ /** * 假如推中为关联数组 保留学生信息 依据成绩排名 * ['name'=>'Bob',score=>99.2] * * @param mixed $value1 * @param mixed $value2 * * @return int */ protected function compare($value1, $value2) { if ($value1['score'] > $value2['score']) { return 1; } elseif ($value1['score'] < $value2['score']) { return -1; } else { return 0; } }}$myheap = new MmaxHead();$myheap->insert(['name' => "bob1", "score" => 65]);$myheap->insert(['name' => "bob2", "score" => 34.3]);$myheap->insert(['name' => "bob3", "score" => 99.3]);$myheap->insert(['name' => "bob4", "score" => 23.4]);$myheap->insert(['name' => "bob5", "score" => 55]);$myheap->insert(['name' => "bob6", "score" => 66]);echo "问题最高的是" . PHP_EOL;var_dump($myheap->top());echo "顺次排名：" . PHP_EOL;while (!$myheap->isEmpty()) { var_dump($myheap->extract());}上一篇：双向链表,堆栈,队列 ...

前K个高频元素，这是一个很有代表性的问题，在理论生存中的利用场景其实也很多，比方微博里每天统计实时热点信息等。 先看下题： 给你一个整数数组 nums 和一个整数 k ，请你返回其中呈现频率前 k 高的元素。你能够按 任意程序 返回答案。 示例 1: 输出: nums = [1,1,1,2,2,3], k = 2输入: [1,2] 进阶：你所设计算法的工夫复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 <!--more--> 这道题的进阶要求工夫复杂度要优于O(nlogn)，那个别的快排，归并等就能够摈弃了。 而对于logn这个工夫复杂度咱们能很疾速的联想到二分，二叉搜寻树和堆。前两个想了下本场景实用不了。 使用堆因而咱们来推导下堆是否能够小于O(nlogn)？答案是必定的，堆能够在O(nlogk)(k<n)的工夫复杂度下等到后果. 桶排序那除了堆，咱们还有其余方法解决么？当然是有的，那就是桶排序。 思路咱们来理一下为什么能够用堆和桶排序两种实现失去答案。我的推导过程如下，大家能够当做参考，有好的计划也欢送和我探讨。 首先要统计前k个高频元素，咱们必须至多要将整个数组遍历一次。这个咱们很快就想到Map去记录每个元素呈现的次数，这个在字母异位词那题外面做过。 而后须要去从Map外面的value进行排序，排序后从大到小的前k个元素就是后果。而造成解法差别就是在排序的实现上。 你能够是各种排序，快排，归并，插入，桶，冒泡，希尔，堆排序等，而各种排序的工夫复杂度决定了最初的工夫复杂度。 而后因为在各个排序里小于进阶要求O(nlogn)的就只有堆排序的O(nlogk)和桶排序的O(n). 具体实现堆法一int[] topK = new int[k];Map<Integer, Integer> countMap = new HashMap<>();//第一个为数组值，第二个为呈现次数PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o2[1]-o1[1]));for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1);}for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) { int value = entry.getKey(), count = entry.getValue(); priQueue.offer(new int[]{value, count});}for (int i = 0; i < k; i++) { topK[i] = priQueue.poll()[0];}return topK;这个是我一开始写的一种谬误的写法，应该是初学者比拟容易犯的谬误。这个解法的工夫复杂度是O(nlogn)而不是O(nlogk)，至于为什么，看下一个解法我会阐明。而且这外面PriorityQueue的泛型类型用的是int[]，这个写的其实还是有点不优雅的，没必要新开构造去记录，间接用现有的Map.Entry<Integer,Integer>即可。 ...

1. 前言想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手。非线性表（树、堆），可以说是前端程序员的内功，要知其然，知其所以然。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 非线性表中的树、堆是干嘛用的 ？其数据结构是怎样的 ？ 希望大家带着这两个问题阅读下文。 2. 树 树的数据结构就像我们生活中的真实的树，只不过是倒过来的形状。 术语定义 节点：树中的每个元素称为节点，如 A、B、C、D、E、F、G、H、I、J。父节点：指向子节点的节点，如 A。子节点：被父节点指向的节点，如 A 的孩子 B、C、D。父子关系：相邻两节点的连线，称为父子关系，如 A 与 B，C 与 H，D 与 J。根节点：没有父节点的节点，如 A。叶子节点：没有子节点的节点，如 E、F、G、H、I、J。兄弟节点：具有相同父节点的多个节点称为兄弟节点，如 B、C、D。节点的高度：节点到叶子节点的最长路径所包含的边数。节点的深度：根节点到节点的路径所包含的边数。节点层数：节点的深度 +1（根节点的层数是 1 ）。树的高度：等于根节点的高度。森林： n 棵互不相交的树的集合。 高度是从下往上度量，比如一个人的身高 180cm ，起点就是从 0 开始的。深度是从上往下度量，比如泳池的深度 180cm ，起点也是从 0 开始的。高度和深度是带有度字的，都是从 0 开始计数的。而层数的计算，是和我们平时的楼层的计算是一样的，最底下那层是第 1 层，是从 1 开始计数的，所以根节点位于第 1 层，其他子节点依次加 1。 二叉树分类 二叉树每个节点最多只有 2 个子节点的树，这两个节点分别是左子节点和右子节点。如上图中的 1、 2、3。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。以此类推，自己想四叉树、八叉树的结构图。 满二叉树一种特殊的二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。如上图中的 2。完全二叉树一种特殊的二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。如上图的 3。完全二叉树与不是完全二叉树的区分比较难，所以对比下图看看。 堆之前的文章 栈内存与堆内存 、浅拷贝与深拷贝 中有说到：JavaScript 中的引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。 ...

栈的定义栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。（百科全书） 栈的常用操作<font size="3">栈中有两个基本的操作 推入 ：从栈的顶端推入一个数据，依次往下推弹出 ：讲栈顶端的数据移除栈的基本提点就是 先进后出，后进先出除了头尾的节点，每个元素都有一个先驱和一个后继对于栈的画面的理解，可以想象成一个步枪弹夹添加子弹和射击的过程弹夹只有一个出入口进行推入和弹出</font> js模拟实现一个栈<body style='width: 80%;height:80%; margin: 10% auto;'><ul id="stackBox" style="width:100px;border:1px solid #1fb19e;"></ul><div style="width:400px; display:flex;"> <input id="funStackBox" value="执行函数"> <div style="margin-left:100px;"> <button onclick="pushStack()" type='primary'>进栈</button> <button onclick="popStack()" type='primary'>出栈</button> </div></div><script> // 栈盒子 let stackBox = document.getElementById('stackBox') // 执行函数盒子 let funStackBox = document.getElementById('funStackBox') // 栈类 class Stack { constructor(length) { this.list = [] this.length = length } // 新增栈 addStack(val) { if (this.length > this.list.length) { this.list.push(val) let beforeDom = document.getElementById(this.list.length - 1) // 新增栈 let el = document.createElement('li') el.id = this.list.length el.innerText = this.list[this.list.length - 1] stackBox.insertBefore(el, beforeDom) }else{ console.log('栈满了') } } // 弹出栈 popStack() { let delDom = document.getElementById(this.list.length) stackBox.removeChild(delDom) return this.list.pop() } // 栈的大小 stackLength() { console.log('当前栈大小为'+this.list.length) return this.list.length } // 栈的顶层元素 stackIsHas() { return this.list.length?this.list[this.list.length]:console.log('没有栈了') } //查看所有元素 showStack() { return this.list.join('\n'); } //清空队列 clearStack() { this.list = []; this.showStack() console.log('栈空了') } } stackOne = new Stack(5) /** * @author: 周靖松 * @information: 进栈 * @Date: 2019-06-10 12:47:16 */ function pushStack() { stackOne.addStack(funStackBox.value) console.log(funStackBox.value, '进栈') stackOne.stackLength() stackOne.stackIsHas() } /** * @author: 周靖松 * @information: 出栈 * @Date: 2019-06-10 12:47:16 */ function popStack() { let popStack = stackOne.popStack(funStackBox.value) console.log(popStack, '出栈') stackOne.stackLength() stackOne.stackIsHas() }</script></body><font size="3">效果图如下</font> ...

前言想写好前端，先练好内功。栈内存与堆内存 、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 栈 定义 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的栈结构。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。不包含任何元素的栈称为空栈。栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。 堆定义 堆数据结构是一种树状结构。它的存取数据的方式，与书架与书非常相似。我们不关心书的放置顺序是怎样的，只需知道书的名字就可以取出我们想要的书了。好比在 JSON 格式的数据中，我们存储的 key-value 是可以无序的，只要知道 key，就能取出这个 key 对应的 value。 堆与栈比较 堆是动态分配内存，内存大小不一，也不会自动释放。栈是自动分配相对固定大小的内存空间，并由系统自动释放。栈，线性结构，后进先出，便于管理。堆，一个混沌，杂乱无章，方便存储和开辟内存空间。栈内存与堆内存JavaScript 中的变量分为基本类型和引用类型。 基本类型是保存在栈内存中的简单数据段，它们的值都有固定的大小，保存在栈空间，通过按值访问，并由系统自动分配和自动释放。这样带来的好处就是，内存可以及时得到回收，相对于堆来说，更加容易管理内存空间。JavaScript 中的 Boolean、Null、Undefined、Number、String、Symbol 都是基本类型。 引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。JavaScript 中的 Object、Array、Function、RegExp、Date 是引用类型。 结合实例说明 let a1 = 0; // 栈内存let a2 = "this is string" // 栈内存let a3 = null; // 栈内存let b = { x: 10 }; // 变量 b 存在于栈中，{ x: 10 } 作为对象存在于堆中let c = [1, 2, 3]; // 变量 c 存在于栈中，[1, 2, 3] 作为对象存在于堆中 ...

前言堆排序是排序算法中的一种，算法时间复杂度是O(n log(n))。这里主要介绍堆的构建以及怎样通过heapify操作完成堆排序。代码是用C语言完成的，算法不难，大家可以自己用其他语言实现一下。 什么是堆（Heap）Heap需要满足两个条件： 1.Complete Binary Tree :需要是一颗完全二叉树2.Parent > Children:父节点的值一定要大于子节点的值什么是完全二叉树 生成节点的顺序是从上往下、从左往右依次生成 如下图所示： 父节点的值大于子节点的值 如下图所示： 怎么样用代码表示堆1.假设先有这样一颗完全二叉树，它已经是一个堆了 2.1 我们按照从上往下、从左往右的顺序对每个节点数字进行编号，2.2 我们可以用一个一维数组表示 2.3 使用数组的下标来表示一个完全二叉树的好处就是从任何一个节点出发我都可以通过计算来拿到这个节点的父节点和子节点 构建堆1.假设拿到了一堆数字：10 4 3 5 1 2，这些数字放在了一颗完全二叉树上面，如下图所示： 2.heapify: 把完全二叉树调整成堆，我们把这种操作起个名字叫：heapify 1.第一次heapify操作：把4（父节点）、10、3这三个子节点进行比较，找到最大值和父节点进行交换交换后如下图: 2.第二次heapify操作,把4（父节点）、5、1这三个子节点进行比较，找到最大值和父节点进行交换交换后如下图: 3.这样我们就生成了一个堆：满足完全二叉树、父节点值大于子节点的值 123步的代码实现： void swap(int *tree, int max, int i) { int temp = tree[i]; tree[i] = tree[max]; tree[max] = temp; } /** 对一个二叉树进行heapify操作 @param tree 表示二叉树的数组 @param n 二叉树的节点个数 @param i 表示要对哪个节点进行heapify操作 */ void heapify(int *tree, int n, int i) { if (i >= n) { // 递归函数出口 return; } // 找到i节点的两个子节点 int c1 = i*2 + 1; int c2 = i*2 + 2; // 找个三个节点的最大值 假设i是最大值 int max = i; if(c1 < n && tree[c1] > tree[max]) { // c1 < n 表示节点下面没有子节点 max = c1; } if (c2 < n && tree[c2] > tree[max]) { max = c2; } if (max != i) { // max != i b如果i已经是最大值了就不用交换了 swap(tree, max, i); heapify(tree, n, max);//max节点继续heapify } } int main(int argc, const char * argv[]) { @autoreleasepool { int tree[] = {4,10,3,5,1,2}; int n = 6; heapify(tree, n, 0); for (int i = 0; i < n; i++) { printf("%d\n", tree[i]); } } return 0; }输出结果： ...

栈和堆的区别中文原文：栈和堆的区别英文原文：Memory：Stack vs Heap 校对：xiaobai22 目录 栈和堆的区别栈堆栈和堆的优缺点 栈堆例子什么时候使用堆关联文章栈和堆的区别到目前为止，我们已经知道如何声明基础变量类型，例如：int,double 等以及复杂类型例如：数组和结构体。在C语言中，我们使用和其他语言诸如MATLAB,Python相同的语法声明它们，并把这些变量推到栈里。 栈什么是栈？这是计算机内存的特定区域，它存储每个函数创建的临时变量（包括main() 函数）。栈使用“LIFO”数据结构，由CPU管理和优化。每当函数声明一个新变量，它就会被推入栈。当函数退出时，所有被该函数推入栈的变量会被释放（这代表，它们已经被删除）。一旦栈的变量释放，此内存区可以被其他栈变量使用。 使用栈保存变量的优点：CPU帮你管理内存。你不需要手动分配和释放。更重要的是，CPU可以高效的组织内存，读写栈变量会非常快。 理解栈的关键 ：当函数退出时，它推入栈的所有变量会被弹出（永远丢失）。栈变量本质是局部的。这涉及到我们之前了解的 变量作用域 或 局部和全局变量。在C语言编程通常会遇到此类BUG：从函数外部企图读取函数内部的变量（在函数退出之后）。 栈另一个需要注意的特征是：保存在栈的变量是有大小限制的。堆的情况却不一样。 栈的总结： 栈的增长和缩容发生在函数推入和弹出局部变量时不需要你自己管理内存，变量会自动分配和释放栈有大小限制栈变量仅存在于创建它们的函数运行的时候堆堆是计算机的内存区，它不会帮你自动管理，也不由CPU管理。堆有更大的空间。你需要使用 C语言内置函数malloc()和 calloc() 分配内存到堆。当不再使用这块内存时，你负责使用free()进行释放。如果没做这步，你的程序会发生内存泄露。堆上的内存仍然被占用（不能被其他进程使用）。正如我们在调试中看到的，用 valgrind工具，帮助检测内存泄漏。 和栈不一样，堆没有大小限制（除了物理内存限制）。堆的读写稍微比较慢，因为必须使用指针访问堆上的内存。我们在后面会讨论指针。 和栈不一样，其他函数和你程序上的任何地方都可以访问堆上创建的变量。堆本质是全局的。 栈和堆的优缺点栈访问非常快不必显式的分配变量CPU有效的管理，不会产生内存碎片仅用于局部变量有大小限制（不同操作系统有区别）大小不能被调整堆变量可以全局访问没有内存限制（相对的）访问速度比较慢会产生内存碎片需要你分配和释放大小可以通过 realloc() 调整例子这是一个简短的程序，创建变量到栈。 #include double multiplyByTwo (double input) { double twice = input * 2.0; return twice;}int main (int argc, char *argv[]){ int age = 30; double salary = 12345.67; double myList[3] = {1.2, 2.3, 3.4}; printf("double your salary is %.3f\n", multiplyByTwo(salary)); return 0;}double your salary is 24691.340在10，11，12行我们声明了变量：int ，double，长度为3的浮点型数组。main() 进行分配的时候，这3个变量被推到栈。当main() 函数退出（程序停止），这些变量会被弹出栈。同样的，在函数 multiplyByTwo() 有2个 double 型的变量，会被推到栈。multiplyByTwo() 退出，这2个变量会被弹出栈，永远消失。 ...

了解和学习一种知识的最好方法是带着相关的问题去探索，当我们把一些常见的问题全部解答了，我们也就能对这种事物有一些初步的了解了。试着回答下面的几个问题，让我们对数据结构和算法有一个基本的认识吧。 什么是数据结构？为什么要了解数据结构？作为一个前端，日常工作当中，我们接触的数据结构有哪几种？数据结构和算法是什么关系？如何判断一个算法是否是最优？什么是数据结构？从字面意思来理解就是一种数据的多种表现方法，什么是结构——由组成整体的各部分的搭配和安排（百度百科）。我的理解是：数据的排列，不同的数据结构就是数据的多种排列形式，然后根据排列的情况我们通常用一个学名来表示它，比如说：数组，集合，树，图等。 为什么要了解数据结构？当我们了解了数据结构之后，在实际的编程过程当中，我们遇到某一类的数据的时候，我们就能够找到一种最合适的数据结构来表示他们了。这样再处理跟数据相关问题的时候就会变得高效，因为确定了数据结构，我们也就确定了针对该结构的数据，使用那些方法来对数据进行相关的操作了。比如说，我们需要一种数据结构来记录每天的天气情况，当我们说到某一天的时候，就能立刻知道当天的天气是怎么样的时候我们可以用一个数组来表现。又如，我们要描述一个家族的族谱的时候，用树型结构比较合适；描述一个人的年龄，身高，体重，民族，学历这种用集合比较合适；描述排队的情况用队列。 作为前端，通常我们接触到的数据结构有哪几种？最常用的应该有两种了：数组，对象。到了ES6又增加了两种新的数据结构Set和Map，其实Set和Map应该算是数组和对象的一种变种，但总的来说它们又是另外两种类型的数据结构； Set类数组结构——成员唯一，没有重复的值Map类对象结构——不同Object，键值通常是字符串，Map的键值可以是任何类型。数据结构和算法的关系数据结构只不过是我们描述数据的一种手段，但我们最终的目的通常是对这些数据进行相关的操作，比如：添加，删除，查找，排序等。所谓的算法就是如何去实现这种操作的一种计算方式。但算法往往不止一种，有道是条条道路通罗马，通常要达到某种目的，我们可能会有很多种的算法。比如一个数组我们要给他进行去重，就有很多种方法。你可以循环遍历，把每个值跟其他的值比较一遍，也可以把数组转成Set结构的数据。 如何判断一个算法是否最优？上面说到实现某种操作的方法有很多种，但是哪一种是最好的，我们要如何判断呢。我们可以通过算法的执行时间对吧，那种算法执行的速度越快，当然那种算法就最好。但计算机当中，还要考虑到算法的空间复杂度，也就是算法执行过程当中，可能占用的内存空间，一个算法执行的速度非常块，但执行的时候，需要1T的内存空间，这就不行。所以好的算法往往有两个条件: 运算的速度快占用的内存（存储空间） 小我还有个第三点，那就是代码便于理解，但这部分优秀的算法，往往涉及到很多数学相关的问题，如果没有这部分相关的概念，理解起来是非常不容易的。 其它涉及到前端数据结构和算法的一些学习笔记，我放到了github上面，内容还在更新，尽量一周分享一个，欢迎大家一起来讨论并参与分享，github地址如下: https://github.com/mmcai/Stru...

行业内接入网络去堆叠已经逐步成为主流方向，在大型互联网公司也已经批量部署。但由于京东集团不同的业务需求及历史原因，没有条件完全复制目前主流的ARP转主机路由方式的去堆叠方案，这促使我们设计一种尽可能满足各类业务需求的方案。近几年来云市场迅速发展，越来越多的用户把关键应用甚至全部应用部署到公有云上。云服务商在产品收入快速增长同时，也深刻体会到产品的高可用性对用户发展和用户留存的重要性。面向用户的产品SLA的实现效果取决于其依赖的各个环节，而基础网络是所有产品需要依赖的一个重要环节，因此，提升网络高可用SLA对整体提升产品整体SLA有着重要促进作用。今天我们要谈的异构去堆叠就是京东云在提高网络高可用SLA方面的新技术研究。用户自有网络其实也面临同样的问题，有提高网络可靠性需求的用户可以考虑在自有网络中使用类似方案。网络高可用通用解决方案首先，让我们先来看一下为了实现网络高可用，当下的四种服务器连接主流方案：由上图可以看出，双网卡/交换机堆叠和双网卡/去交换机堆叠提供了更好的高可用保证。通用堆叠方式 V.S 通用去堆叠方式01 堆叠方案优势服务器双网卡捆绑，无需特别改造交换机控制面统一，支持服务器BGP路由方式接入劣势多设备统一控制面，可靠性低升级困难横向连接浪费端口02 去堆叠方案常见的去堆叠方案有以下两种：去堆叠方案-路由方式优势交换机完全独立支持异构路由方式接入的服务器无需特别改造劣势2层方式接入的服务器需要进行改造服务器除网卡IP外需配置单独业务IP服务器多IP增加业务方运维复杂度静态路由方式不适合VM或Docker漂移动态路由方式要求全部服务器运行路由协议2.去堆叠方案-ARP转主机路由方式优势交换机完全独立服务器网卡捆绑方式不变，便于运维服务器网卡捆绑方式不变，便于运维劣势一组交换机要求同厂商，不支持异构需要修改服务器Linux内核ARP处理部分不支持服务器BGP路由方式接入通过以上对比，可以发现堆叠与去堆叠方式其实都可以实现网络的高可用，但各有利弊。针对这样的情况，京东云提出了一种理想的去堆叠方式，可以满足下图中的所有需求。异构去堆叠方案01 实现方法交换机侧IP配置/24掩码，两台交换机可配置相同IP或者不同IP；启用ARP代理及转主机路由功能；配置ARP超时时间为5s以便在服务器不响应ARP时快速撤回主机路由。服务器侧服务器双网卡配置相同IP地址（掩码/32）；采用onlink方式配置目的为交换机IP的静态路由指向对应网卡；采用onlink方式配置缺省路由同时指向两块网卡；需要运行Ifplugd进程监控物理连接，物理连接发生UP/DOWN时执行相应ARP Ping和路由修改操作。02 冗余测试从上图中的测试拓扑和结果中可以看出，不论是软件操作上的禁用还是硬件拔出，在设定的收敛时间内，服务器的网络一直保持高可用。03 异构去堆叠方案小结异构去堆叠方案优势交换机完全独立异构避免单一厂商风险异构推动自研交换机快速上线服务器侧支持2层方式或BGP路由方式不修改Linux内核注意事项需要内核版本支持L4 HASH方式ECMP（Centos 7.4以上）需要运行Ifplugd进程监控物理连接总结综上所述，异构去堆叠有助于实现苛刻的网络SLA和极致的用户体验。京东云在设计去堆叠方案时首先考虑了异构，一方面因为单一厂商对网络高可用SLA还是一个重要风险点，另一方面异构方式可以促进京东正在进行的自研交换机实现快速部署。众所周知，自研交换机在各大互联网公司都是重点项目，但软件和硬件的稳定性一直是批量部署的重大障碍。而异构去堆叠利用自研和商用交换机1+1的方式可以大大降低自研交换机稳定性的影响。·END·

定义堆是一种特别的树状结构，我们首先来看看维基百科的上定义。堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。总结来说，堆是一个完全二叉树，最多只有两个子节点，并且必须保证根节点是最大的值或者最小的值，所以对于一个堆而言，根节点是最大的值或者是最小的值。存储因为堆是一棵完全二叉树，所以使用数组可以高效的存储数据。对于使用数组存储的方式，有两个性质非常关键，对于一个非根节点的节点i来说，如果它的下标为k，那么它的父节点的下标为 (k -1)/2，子节点的下标为2 *k +1和2 *k + 2基本操作堆化插入删除堆化对于任意一个无序数组而言，实现堆化的步骤如下，我们以构建一个最大堆为例：找到第一个非叶子节点，对这个节点的左子树和右子树与节点比较，将大的元素放置到父节点的位置，直到父节点已经是最大值或者改节点已经是叶子节点。依次对所有的非叶子节点进行第一步的操作private Heap(int[] data){ int last_p = data.length - 1; //i是第一个非叶子节点 for (int i = (last_p - 1) / 2; i >= 0; i–) { heapify(data, i, last_p); } this.data = data;}private void heapify(int[] data, int start, int end){ int value = data[start]; int current_p = start; //左孩子 int left_p = 2 * current_p + 1; while (left_p <= end) { //右节点大于左节点 if (left_p < end && data[left_p] < data[left_p + 1]) { //移动位置到右节点 left_p++; } //当前的父节点已经是最大值 if (data[left_p] < value) { break; } else { //子节点上移到父节点的位置 data[current_p] = data[left_p]; current_p = left_p; left_p = current_p * 2 + 1; } } data[current_p] = value;}插入插入的算法如下：.将新增的节点放在数组的最末端，也就是数组的最后一个位置。然后计算出父节点的位置，让当前节点与父节点比较，如果父节点比较小，交换位置。重复上述步骤，直到父节点大于当前节点或者当前节点是根节点。public int insert(int value){ checkSize(); int position = data.length - 1; data[position] = value; int current_p = position; int parent_p = (position - 1) / 2; while (current_p > 0) { if (data[parent_p] > value) { break; } else { data[current_p] = data[parent_p]; current_p = parent_p; parent_p = (current_p - 1) / 2; } } data[current_p] = value; return position;}删除删除的算法如下：将数组最后一个节点与当前需要删除的节点替换，删除最后一个节点，对于替换的节点来说，相当于进行了依次插入操作，不过这次是从上往下的插入。算法与remove相同，也是比较最大的值进行替换，直到不满足条件为止。删除根节点public int remove(){ int root = data[0]; int last = data[data.length - 1]; data[0] = last; data = Arrays.copyOf(data, data.length - 1); if (data.length == 0) { return root; } //从顶点开始调整 int current_p = 0; int l = current_p * 2 + 1; int value = data[current_p]; while (l < data.length) { if (l < data.length - 1 && data[l] < data[l + 1]) { l++; //右孩子大 } if (data[l] <= value) { break; } else { data[current_p] = data[l]; current_p = l; l = current_p * 2 + 1; } } data[current_p] = value; return root;}应用堆应用比较多的一个用处就是堆排序，对于一个数组进行堆化之后，第一个数组是最大的值，然后交换第一个数和最后一个数，这样最大的数就落在了最后一个数组的位置。缩小数组，重复之前的步骤，最后就得到了一个排序好的数组。int[] data = new int[] {20, 40, 80, 33, 111, 47, 21, 90, -1};HeapSort hs = new HeapSort();hs.heap_array(data, data.length - 1);for (int i = 0; i < data.length - 1; i++){ int tmp = data[0]; data[0] = data[data.length - 1 - i]; data[data.length - 1 - i] = tmp; hs.heap_array(data, data.length - 2 - i);}System.out.println(Arrays.toString(data));代码地址： https://gitee.com/devnew/Algo… ...

你好，是我琉忆，PHP程序员面试笔试系列图书的作者。本周（2019.3.18至3.22）的一三五更新的文章如下：周一：PHP面试常考之数据结构——链表的概念周三：PHP面试常考之数据结构——栈和队列周五：PHP面试常考之数据结构——自己整理了一篇“PHP如何实现链表？”的文章，关注公众号：“琉忆编程库”，回复：“链表”，我发给你。一、链表链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表有很三种不同的类型：单向链表，双向链表以及循环链表。二、单向链表单向链表包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。如图：三、双向链表每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）如图：四、循环链表在一个循环链表中,首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存，假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。指向整个列表的指针可以被称作访问指针。自己编写的《PHP程序员面试笔试宝典》和《PHP程序员面试笔试真题解析》书籍，已在各大电商平台销售，两本可以帮助你更快更好的拿到offer的书。更多PHP相关的面试知识、考题可以关注公众号获取：琉忆编程库对本文有什么问题或建议都可以进行留言，我将不断完善追求极致，感谢你们的支持。

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。且完全二叉树可以基于数组存储（父子节点的关系可以用数组下标表示），加持上堆的特性，故可以做堆排序。满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；即每一层节点数都达到最大值；即深度为 k 的二叉树节点个数为 2^k-1，则为满二叉树；完全二叉树：若设二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，且第 k 层所有的结点都连续集中在最左边，这就是完全二叉树。堆：基于完全二叉树，分为大顶堆/小顶堆。各节点的数值皆大于其左右子节点的数值（大顶堆），或各节点的数值皆小于其左右子节点的数值（小顶堆）堆的特性大顶堆，节点的数值皆大于子节点的数值，下文都以大顶堆为实例讲解。因为是基于完全二叉树的，所以堆还有一些相应的特性：1、位序为 n 的节点，其父节点位序为 (int) n/22、位序为 n 的节点，其左子节点位序为 2n，右子节点位序为 2n+1（这是按照位序从1开始计算，但对编程语言不太友好，如果位序从0开始计算，则左子节点位序为 2n+1, 右子节点位序为 2n+2）按照数组下标的方式去编号的话如下： 0 / \ 1 2 / \ / \ 3 4 5 6 … / floor(n/2) … / n / \2n+1 2n+2可以发现，所有非叶子节点的序号都会落在 0 ~ (int) N/2-1 区间中，N为节点总数，例如：1、有4个节点，节点编号为03，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。2、有5个节点，节点编号为04，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。3、有6个节点，节点编号为05，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。4、有7个节点，节点编号为06，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。可以很方便的获取完全二叉树的非叶子节点的序号集合，从 k-1 层开始，依次将各非叶子节点及其左右子节点视为一个完全二叉树，将其调整至大顶堆，直至根节点，这时整个二叉树就是一个大顶堆我们有了非叶子节点的序号及获取左右节点序号的算式，所以很容易就可以将各非叶子节点及其左右子节点组成的完全二叉树调整至大顶堆。同时要注意如果非叶子节点同其左右子节点发生了调整，其左右子节点如果也是非叶子节点的话，也要检测是否破坏了堆特性，如破坏也需进行调整。堆排序堆排序：将初始待排序关键字序列(R0,R1….Rn-1)构建成大顶堆，此堆为初始的无序区将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R1,…,Rn-2)和新的有序区(Rn-1),且满足R[1,2…n-2]<=R[n-1]由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,…,Rn-2)调整为新堆，然后再次将R[0]与无序区最后一个元素交换，得到新的无序区(R0,R1….Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1（第n-1次调整时完全二叉树只有2个节点，即可有序化），则整个排序过程完成。即堆排序的过程:将待排序数组映射到完全二叉树中，通过调整完全二叉树至大顶堆，获取根节点的值（节点最大值）。那大顶堆的构建如何做呢？我用比较白话的方式讲一下1、从 k 层开始，将每一层子节点的最大值与其父节点的值进行比较调整（如发生交换且子节点为非叶子节点，也要检查子节点的树是否满足了父节点大于子节点的特性）2、重复第一步骤直到根节点，此时根节点的值即为完全二叉树节点中的最大值，即生成了大顶堆源码实例package mainimport ( “fmt”)func main() { // 待排序数组 go 的数组传参是值拷贝 我们用切片引用传值更方便些 var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8} HeapSort(arr) fmt.Print(arr)}// 堆排序func HeapSort(arr []int) { arrLength := len(arr) // 每一次的堆构建都能得到一个节点中的最大值（根节点）对于N个待排序数列，N-1次堆构建即可得出有序数列 for i := 0; i < arrLength; i++ { // 无序区长度 arrLengthUnsorted := arrLength - i // 无序区构建为完全二叉树后非叶节点的下标的范围 unLeafNodeIndexRange := int(arrLengthUnsorted/2 - 1) // 从 k - 1 层开始 将非叶节点的子树分治递归构建成大顶堆 for j := unLeafNodeIndexRange; j >= 0; j– { HeapBuild(arr, j, arrLengthUnsorted) } // 打印下标 0 ~ arrLengthUnsorted-1 的数列 fmt.Println(“current heap: “, arr[0:arrLengthUnsorted]) // 一次大顶堆构建完成，根节点为堆最大值，与无序区堆的最后一个节点交换 // 无序区节点数-1 // 破坏了堆结构 开始对新无序区做大顶堆构建 SwapItemOfArray(arr, 0, arrLengthUnsorted-1) }}// 将子树调整为大顶堆func HeapBuild(arr []int, nodeIndex int, arrLengthUnsorted int) { // 完全二叉树子节点下标同父节点下标的关系式 leftChildNodeIndex, rightChildNodeIndex := nodeIndex2+1, nodeIndex2+2 // 防止子节点下标越界 && 子节点数值大于父节点 则交换节点值 if leftChildNodeIndex < arrLengthUnsorted && arr[leftChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, leftChildNodeIndex, nodeIndex) HeapBuild(arr, leftChildNodeIndex, arrLengthUnsorted) //左子树根节点改变 需调整堆结构 } if rightChildNodeIndex < arrLengthUnsorted && arr[rightChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, rightChildNodeIndex, nodeIndex) HeapBuild(arr, rightChildNodeIndex, arrLengthUnsorted) //右子树根节点改变 需调整堆结构 }}// 交换数组两个元素func SwapItemOfArray(arr []int, indexX int, indexY int) { temp := arr[indexX] arr[indexX] = arr[indexY] arr[indexY] = temp} ...