|
|
|
|
知识点：
数据结构
堆
|
|
关键词：
数据结构
数据
章/节：
嵌入式操作系统基础知识
|
|
|
|
|
|
|
|
堆是一种有用的数据结构，下列关键字序列中，(51)是一个堆。
|
|
|
|
|
| A.
16,72,31,23,94,53
|
|
|
| B.
94,53,31,72,16,53
|
|
|
| C.
16,53,23,94,31,72
|
|
|
| D.
16,31,23,94,53,72
|
|
|
|
|
|
|
|
| |
|
为保障您的权益，请登录
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
.页表：页表给出了任务的逻辑页面号与内存中的物理页面号之间的对应关系。
|
|
|
|
.物理页面表：用来描述内存空间中各个物理页面的使用分配状况。在具体实现上，可以采用位示图或空闲页面链表等方法。
|
|
|
|
下图是页表的一个例子。在任务的逻辑地址空间当中，总共有4个页面，即页面0、页面1、页面2和页面3。页表描述的是逻辑页面号与物理页面号之间的对应关系，即每一个逻辑页面存放在哪一个物理页面中。页表的下标是逻辑页面号，从0到3。相应的页表项存放的就是该逻辑页面所对应的物理页面号。在本例中，任务的4个逻辑页面分别存放在第1、第4、第3和第7个物理页面中。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n个元素的序列{k1, k2, …, kn｝当且仅当满足以下的关系式时才称之为堆： 或 ，并相应地称为小顶堆或大顶堆。
|
|
|
|
|
|
判断堆的办法是把序列看成一棵完全二叉树，若树中所有非终端节点的值均不大于（或不小于）其左右孩子的节点的值，则该序列为堆。
|
|
|
|
|
|
堆的典型应用是堆排序。堆排序首先要根据待排序记录的关键字建立初始堆，其方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，显然所有i>［n/2］的节点ki都没有子节点，以这样的ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=［n/2］）个节点开始，通过调整，逐步使以k[n/2]， k［n/2]-1, …, k2, k1为根的子树满足堆的定义。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
