原文:
是的扩展，具有以下属性:
- 每个项目都有一个相关的优先级。
- 优先级高的元素在优先级低的元素之前出队。
- 如果两个元素具有相同的优先级，则根据它们在队列中的顺序提供服务。
一个是一个二叉树，具有以下属性:
- 是。二进制堆的这个属性使得它们适合存储在数组中。
- 二进制堆要么是最小堆要么是最大堆。
- 在最小二进制堆中，根的键必须是二进制堆中所有键中最小的。相同的属性必须递归地适用于二叉树中的所有节点。
- 类似地，在最大二进制堆中，根的键必须是二进制堆中所有键中最大的。对于二叉树中的所有节点，相同的属性必须递归为真。
对二进制堆的操作
- 插入(p): 插入具有优先级的新元素 p 。
- extractmax(): 提取具有最大优先级的元素。
- 移除(i): 移除迭代器 i 指向的元素。
- getmax(): 返回优先级最高的元素。
- 更改优先级(i，p): 将 i 指向的元素的优先级更改为 p 。
二进制最大堆示例
- 假设下面是遵循二进制最大堆所有属性的给定二进制堆。
- 现在需要在上面的堆中插入一个值为 32 的节点:要插入一个元素，将新元素附加到任何叶子上。例如一个优先级为 32 的节点可以添加到节点 11 的叶子中。但是这违反了堆属性。要维护堆属性，上移新节点 32 。
- 【上移操作】在正确的位置获取 32 的节点: 将放置不正确的节点与其父节点交换，直到满足堆属性。例如:由于节点 11 小于节点 32 所以，交换节点 11 和节点 32 。然后，交换节点 14 和节点 32 。最后，交换节点 31 和节点 32 。
- extractmax: 最大值存储在树根处。但是树根不能直接去掉。首先，用任何一片叶子替换它，然后去掉。例如:要去掉节点 45 ，先用节点 11 替换。但是这违反了堆属性，所以下移被替换的节点。为此，请使用降档操作。
- 【shift down】操作: 用一个更大的子节点交换错误放置的节点，直到满足堆属性。例如:节点 11 与节点 32 交换，然后与节点 31 交换，最后与节点 14 交换。
- 变更优先级: 让变更后的元素根据其优先级是降低还是升高而上下移动。例如:将节点的优先级 11 更改为 35 ，由于此更改，节点必须上移节点以维护堆属性。
- 移除: 要移除元素，请将其优先级更改为大于当前最大值的值，然后将其上移，然后使用 extract max 提取它。使用 getmax 查找当前最大值。
- getmax: 最大值存储在树根处。要获取 max，只需返回树根部的值。
二进制堆的数组表示
由于堆是以完整的二叉树的形式维护的，因此堆可以以数组的形式表示。为了保持树的完整和浅，当插入一个新元素时，把它插入到最后一级最左边的空位置，也就是我们数组的末尾。同样，在提取最大值时，将根替换为最后一级的最后一片叶子，即数组的最后一个元素。下面是同样的插图:
下面是使用二进制堆实现优先级队列的程序:
c
// c code to implement priority-queue
// using array implementation of
// binary heap
#include
using namespace std;
int h[50];
int size = -1;
// function to return the index of the
// parent node of a given node
int parent(int i)
{
return (i - 1) / 2;
}
// function to return the index of the
// left child of the given node
int leftchild(int i)
{
return ((2 * i) 1);
}
// function to return the index of the
// right child of the given node
int rightchild(int i)
{
return ((2 * i) 2);
}
// function to shift up the node in order
// to maintain the heap property
void shiftup(int i)
{
while (i > 0 && h[parent(i)] < h[i]) {
// swap parent and current node
swap(h[parent(i)], h[i]);
// update i to parent of i
i = parent(i);
}
}
// function to shift down the node in
// order to maintain the heap property
void shiftdown(int i)
{
int maxindex = i;
// left child
int l = leftchild(i);
if (l <= size && h[l] > h[maxindex]) {
maxindex = l;
}
// right child
int r = rightchild(i);
if (r <= size && h[r] > h[maxindex]) {
maxindex = r;
}
// if i not same as maxindex
if (i != maxindex) {
swap(h[i], h[maxindex]);
shiftdown(maxindex);
}
}
// function to insert a new element
// in the binary heap
void insert(int p)
{
size = size 1;
h[size] = p;
// shift up to maintain heap property
shiftup(size);
}
// function to extract the element with
// maximum priority
int extractmax()
{
int result = h[0];
// replace the value at the root
// with the last leaf
h[0] = h[size];
size = size - 1;
// shift down the replaced element
// to maintain the heap property
shiftdown(0);
return result;
}
// function to change the priority
// of an element
void changepriority(int i, int p)
{
int oldp = h[i];
h[i] = p;
if (p > oldp) {
shiftup(i);
}
else {
shiftdown(i);
}
}
// function to get value of the current
// maximum element
int getmax()
{
return h[0];
}
// function to remove the element
// located at given index
void remove(int i)
{
h[i] = getmax() 1;
// shift the node to the root
// of the heap
shiftup(i);
// extract the node
extractmax();
}
// driver code
int main()
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
create a priority queue shown in
example in a binary max heap form.
queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// priority queue before extracting max
cout << "priority queue : ";
while (i <= size) {
cout << h[i] << " ";
i ;
}
cout << "\n";
// node with maximum priority
cout << "node with maximum priority : "
<< extractmax() << "\n";
// priority queue after extracting max
cout << "priority queue after "
<< "extracting maximum : ";
int j = 0;
while (j <= size) {
cout << h[j] << " ";
j ;
}
cout << "\n";
// change the priority of element
// present at index 2 to 49
changepriority(2, 49);
cout << "priority queue after "
<< "priority change : ";
int k = 0;
while (k <= size) {
cout << h[k] << " ";
k ;
}
cout << "\n";
// remove element at index 3
remove(3);
cout << "priority queue after "
<< "removing the element : ";
int l = 0;
while (l <= size) {
cout << h[l] << " ";
l ;
}
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java code to implement
// priority-queue using
// array implementation of
// binary heap
import java.util.*;
class gfg{
static int []h = new int[50];
static int size = -1;
// function to return the index of the
// parent node of a given node
static int parent(int i)
{
return (i - 1) / 2;
}
// function to return the index of the
// left child of the given node
static int leftchild(int i)
{
return ((2 * i) 1);
}
// function to return the index of the
// right child of the given node
static int rightchild(int i)
{
return ((2 * i) 2);
}
// function to shift up the
// node in order to maintain
// the heap property
static void shiftup(int i)
{
while (i > 0 &&
h[parent(i)] < h[i])
{
// swap parent and current node
swap(parent(i), i);
// update i to parent of i
i = parent(i);
}
}
// function to shift down the node in
// order to maintain the heap property
static void shiftdown(int i)
{
int maxindex = i;
// left child
int l = leftchild(i);
if (l <= size &&
h[l] > h[maxindex])
{
maxindex = l;
}
// right child
int r = rightchild(i);
if (r <= size &&
h[r] > h[maxindex])
{
maxindex = r;
}
// if i not same as maxindex
if (i != maxindex)
{
swap(i, maxindex);
shiftdown(maxindex);
}
}
// function to insert a
// new element in
// the binary heap
static void insert(int p)
{
size = size 1;
h[size] = p;
// shift up to maintain
// heap property
shiftup(size);
}
// function to extract
// the element with
// maximum priority
static int extractmax()
{
int result = h[0];
// replace the value
// at the root with
// the last leaf
h[0] = h[size];
size = size - 1;
// shift down the replaced
// element to maintain the
// heap property
shiftdown(0);
return result;
}
// function to change the priority
// of an element
static void changepriority(int i,
int p)
{
int oldp = h[i];
h[i] = p;
if (p > oldp)
{
shiftup(i);
}
else
{
shiftdown(i);
}
}
// function to get value of
// the current maximum element
static int getmax()
{
return h[0];
}
// function to remove the element
// located at given index
static void remove(int i)
{
h[i] = getmax() 1;
// shift the node to the root
// of the heap
shiftup(i);
// extract the node
extractmax();
}
static void swap(int i, int j)
{
int temp= h[i];
h[i] = h[j];
h[j] = temp;
}
// driver code
public static void main(string[] args)
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
create a priority queue shown in
example in a binary max heap form.
queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// priority queue before extracting max
system.out.print("priority queue : ");
while (i <= size)
{
system.out.print(h[i] " ");
i ;
}
system.out.print("\n");
// node with maximum priority
system.out.print("node with maximum priority : "
extractmax() "\n");
// priority queue after extracting max
system.out.print("priority queue after "
"extracting maximum : ");
int j = 0;
while (j <= size)
{
system.out.print(h[j] " ");
j ;
}
system.out.print("\n");
// change the priority of element
// present at index 2 to 49
changepriority(2, 49);
system.out.print("priority queue after "
"priority change : ");
int k = 0;
while (k <= size)
{
system.out.print(h[k] " ");
k ;
}
system.out.print("\n");
// remove element at index 3
remove(3);
system.out.print("priority queue after "
"removing the element : ");
int l = 0;
while (l <= size)
{
system.out.print(h[l] " ");
l ;
}
}
}
// this code is contributed by 29ajaykumar
python 3
# python3 code to implement priority-queue
# using array implementation of
# binary heap
h = [0]*50
size = -1
# function to return the index of the
# parent node of a given node
def parent(i) :
return (i - 1) // 2
# function to return the index of the
# left child of the given node
def leftchild(i) :
return ((2 * i) 1)
# function to return the index of the
# right child of the given node
def rightchild(i) :
return ((2 * i) 2)
# function to shift up the
# node in order to maintain
# the heap property
def shiftup(i) :
while (i > 0 and h[parent(i)] < h[i]) :
# swap parent and current node
swap(parent(i), i)
# update i to parent of i
i = parent(i)
# function to shift down the node in
# order to maintain the heap property
def shiftdown(i) :
maxindex = i
# left child
l = leftchild(i)
if (l <= size and h[l] > h[maxindex]) :
maxindex = l
# right child
r = rightchild(i)
if (r <= size and h[r] > h[maxindex]) :
maxindex = r
# if i not same as maxindex
if (i != maxindex) :
swap(i, maxindex)
shiftdown(maxindex)
# function to insert a
# new element in
# the binary heap
def insert(p) :
global size
size = size 1
h[size] = p
# shift up to maintain
# heap property
shiftup(size)
# function to extract
# the element with
# maximum priority
def extractmax() :
global size
result = h[0]
# replace the value
# at the root with
# the last leaf
h[0] = h[size]
size = size - 1
# shift down the replaced
# element to maintain the
# heap property
shiftdown(0)
return result
# function to change the priority
# of an element
def changepriority(i,p) :
oldp = h[i]
h[i] = p
if (p > oldp) :
shiftup(i)
else :
shiftdown(i)
# function to get value of
# the current maximum element
def getmax() :
return h[0]
# function to remove the element
# located at given index
def remove(i) :
h[i] = getmax() 1
# shift the node to the root
# of the heap
shiftup(i)
# extract the node
extractmax()
def swap(i, j) :
temp = h[i]
h[i] = h[j]
h[j] = temp
# insert the element to the
# priority queue
insert(45)
insert(20)
insert(14)
insert(12)
insert(31)
insert(7)
insert(11)
insert(13)
insert(7)
i = 0
# priority queue before extracting max
print("priority queue : ", end = "")
while (i <= size) :
print(h[i], end = " ")
i = 1
print()
# node with maximum priority
print("node with maximum priority :" , extractmax())
# priority queue after extracting max
print("priority queue after extracting maximum : ", end = "")
j = 0
while (j <= size) :
print(h[j], end = " ")
j = 1
print()
# change the priority of element
# present at index 2 to 49
changepriority(2, 49)
print("priority queue after priority change : ", end = "")
k = 0
while (k <= size) :
print(h[k], end = " ")
k = 1
print()
# remove element at index 3
remove(3)
print("priority queue after removing the element : ", end = "")
l = 0
while (l <= size) :
print(h[l], end = " ")
l = 1
# this code is contributed by divyeshrabadiya07.
c
// c# code to implement priority-queue
// using array implementation of
// binary heap
using system;
class gfg{
static int []h = new int[50];
static int size = -1;
// function to return the index of the
// parent node of a given node
static int parent(int i)
{
return (i - 1) / 2;
}
// function to return the index of the
// left child of the given node
static int leftchild(int i)
{
return ((2 * i) 1);
}
// function to return the index of the
// right child of the given node
static int rightchild(int i)
{
return ((2 * i) 2);
}
// function to shift up the
// node in order to maintain
// the heap property
static void shiftup(int i)
{
while (i > 0 &&
h[parent(i)] < h[i])
{
// swap parent and current node
swap(parent(i), i);
// update i to parent of i
i = parent(i);
}
}
// function to shift down the node in
// order to maintain the heap property
static void shiftdown(int i)
{
int maxindex = i;
// left child
int l = leftchild(i);
if (l <= size &&
h[l] > h[maxindex])
{
maxindex = l;
}
// right child
int r = rightchild(i);
if (r <= size &&
h[r] > h[maxindex])
{
maxindex = r;
}
// if i not same as maxindex
if (i != maxindex)
{
swap(i, maxindex);
shiftdown(maxindex);
}
}
// function to insert a
// new element in
// the binary heap
static void insert(int p)
{
size = size 1;
h[size] = p;
// shift up to maintain
// heap property
shiftup(size);
}
// function to extract
// the element with
// maximum priority
static int extractmax()
{
int result = h[0];
// replace the value
// at the root with
// the last leaf
h[0] = h[size];
size = size - 1;
// shift down the replaced
// element to maintain the
// heap property
shiftdown(0);
return result;
}
// function to change the priority
// of an element
static void changepriority(int i,
int p)
{
int oldp = h[i];
h[i] = p;
if (p > oldp)
{
shiftup(i);
}
else
{
shiftdown(i);
}
}
// function to get value of
// the current maximum element
static int getmax()
{
return h[0];
}
// function to remove the element
// located at given index
static void remove(int i)
{
h[i] = getmax() 1;
// shift the node to the root
// of the heap
shiftup(i);
// extract the node
extractmax();
}
static void swap(int i, int j)
{
int temp = h[i];
h[i] = h[j];
h[j] = temp;
}
// driver code
public static void main(string[] args)
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
create a priority queue shown in
example in a binary max heap form.
queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// priority queue before extracting max
console.write("priority queue : ");
while (i <= size)
{
console.write(h[i] " ");
i ;
}
console.write("\n");
// node with maximum priority
console.write("node with maximum priority : "
extractmax() "\n");
// priority queue after extracting max
console.write("priority queue after "
"extracting maximum : ");
int j = 0;
while (j <= size)
{
console.write(h[j] " ");
j ;
}
console.write("\n");
// change the priority of element
// present at index 2 to 49
changepriority(2, 49);
console.write("priority queue after "
"priority change : ");
int k = 0;
while (k <= size)
{
console.write(h[k] " ");
k ;
}
console.write("\n");
// remove element at index 3
remove(3);
console.write("priority queue after "
"removing the element : ");
int l = 0;
while (l <= size)
{
console.write(h[l] " ");
l ;
}
}
}
// this code is contributed by amit katiyar
java 描述语言
output:
priority queue : 45 31 14 13 20 7 11 12 7
node with maximum priority : 45
priority queue after extracting maximum : 31 20 14 13 7 7 11 12
priority queue after priority change : 49 20 31 13 7 7 11 12
priority queue after removing the element : 49 20 31 12 7 7 11
时间复杂度:除了时间复杂度为 o(1)的 getmax()外，所有操作的时间复杂度均为 o(log n) 。 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
