堆数据结构

堆是平衡二叉树数据结构的一种特例，其中根节点的键与其子节点进行比较并进行相应的排序。如果 α 有子节点 β 则 −

key(α) ≥ key(β)

由于父节点的值大于子节点的值，此属性生成最大堆。基于此标准，堆可以分为两种类型 −

输入 → 35 33 42 10 14 19 27 44 26 31

最小堆 − 其中根节点的值小于或等于其任一子节点的值。

最大堆 −根节点的值大于或等于其任一子节点的值。

两棵树的构造方法相同，输入和到达顺序也相同。

最大堆构造算法

我们将使用相同的示例来演示如何创建最大堆。创建最小堆的过程类似，但我们选择的是最小值而不是最大值。

我们将通过一次插入一个元素来推导最大堆的算法。在任何时候，堆都必须保持其属性。插入时，我们假设插入节点的是一棵已经堆化的树。

步骤 1 −在堆的末尾创建一个新节点。
步骤 2 − 为该节点分配新值。
步骤 3 − 将此子节点的值与其父节点的值进行比较。
步骤 4 − 如果父节点的值小于子节点的值，则交换它们。
步骤 5 − 重复步骤 3 和 4，直到满足堆的性质。

注意 − 在最小堆构造算法中，我们期望父节点的值小于子节点的值。

让我们通过动画演示来理解最大堆的构造。我们考虑与之前相同的输入样本。

示例

以下是此操作在各种编程语言中的实现 −

//最大堆构造算法的 C 代码
#include 
#include 
// 表示堆的结构体
typedef struct {
    int* array; // 用于存储堆元素的数组
    int capacity; // 堆的最大容量
    int size; // 堆的当前大小
} Heap;
// 创建新堆的函数
Heap* createHeap(int capacity)
{
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->array = (int*)malloc(capacity * sizeof(int));
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 函数用于交换堆中的两个元素
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 函数用于对以索引 i 为根的子树进行堆化
void heapify(Heap* heap, int i)
{
    int biggest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左节点是否大于根
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的子节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        biggest = right;
    // 如果最大的子节点不是根节点，则将根节点与最大的子节点交换
    if (largest != i) {
        swap(&heap->array[i], &heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        printf("Heap is full. Cannot insert more elements.
");
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了堆属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中提取最大元素的函数
int extractMax(Heap* heap)
{
    if (heap->size == 0) {
        printf("Heap is empty. Cannot extract maximum element.
");
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 将根堆化
    heapify(heap, 0);
    return max;
}
// 打印堆元素的函数
void printHeap(Heap* heap)
{
    printf("Heap elements: ");
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->array[i]);
    }
    printf("
");
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
    printHeap(heap);
    int max = extractMax(heap);
    printf("最大元素： %d
", max);
    return 0;
}  

Heap elements: 44 42 35 33 31 19 27 10 26 14 
最大元素： 44

//最大堆构造算法的 C++ 代码
#include 
// 表示堆的结构体
struct Heap {
    int* array; // 用于存储堆元素的数组
    int capacity; // 堆的最大容量
    int size; // 堆的当前大小
};
// 创建新堆的函数
Heap* createHeap(int capacity)
{
    Heap* heap = new Heap;
    heap->array = new int[capacity];
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 交换堆中两个元素的函数
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
// 函数将以索引 i 为根的子树堆化
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左节点是否大于根
    if (left <heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的子节点
    if (right <heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大的不是根，则将根与最大的交换
    if (largest != i) {
        swap(heap->array[i], heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        std::cout << "Heap is full. Cannot insert more elements." << std::endl;
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了堆属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(heap->array[i], heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中提取最大元素的函数
int extractMax(Heap* heap)
{
    if (heap->size == 0) {
        std::cout << "Heap is empty. Cannot extract maximum element." << std::endl;
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 将根堆化
    heapify(heap, 0);
    return max;
}
// 打印堆元素的函数
void printHeap(Heap* heap)
{
    std::cout << "Heap elements: ";
    for (int i = 0; i < heap->size; i++) {
        std::cout << heap->array[i] << " ";
    }
    std::cout << std::endl;
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);

    printHeap(heap);

    int max = extractMax(heap);
    std::cout << "最大元素： " << max << std::endl;

    return 0;
}

Heap elements: 44 42 35 33 31 19 27 10 26 14 
最大元素： 44

// 最大堆构造算法的 Java 代码
// 表示堆的结构
public class MaxHeap {
    private int[] heap; // 存储堆元素
    private int capacity; // 堆的最大容量
    private int size; // 堆的当前大小
    // 创建新堆
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }
    private int parent(int i) {
        return (i - 1) / 2;
    }
    private int leftChild(int i) {
        return 2 * i + 1;
    }
    private int rightChild(int i) {
        return 2 * i + 2;
    }
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
   // 堆化以索引 i 为根的子树
    private void heapifyDown(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);     
        // 检查左节点是否大于根
        if (left < size && heap[left] > heap[largest])
            largest = left;         
        // 检查右子节点是否大于目前最大的子节点
        if (right < size && heap[right] > heap[largest])
            largest = right;
        // 如果最大的不是根，则将根与最大的交换
        if (largest != i) {
            swap(i, largest);
            heapifyDown(largest);
        }
    }
    private void heapifyUp(int i) {
        while (i > 0 && heap[i] > heap[parent(i)]) {
            int parent = parent(i);
            swap(i, parent);
            i = parent;
        }
    }
    // 在末尾插入新元素
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full. Cannot insert more elements.");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }
    // 从堆中提取最大元素的函数
    public int extractMax() {
        if (size == 0) {
            System.out.println("Heap is empty. Cannot extract maximum element.");
            return -1;
        }
        // 存储根元素
        int max = heap[0];
        //用最后一个元素替换根
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    } 
    //打印堆的元素
    public void printHeap() {
        System.out.print("Heap elements: ");
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(10);
        heap.insert(35);
        heap.insert(33);
        heap.insert(42);
        heap.insert(10);
        heap.insert(14);
        heap.insert(19);
        heap.insert(27);
        heap.insert(44);
        heap.insert(26);
        heap.insert(31);
        heap.printHeap();
        int max = heap.extractMax();
        System.out.println("最大元素： " + max);
    }
}

Heap elements: 44 42 35 33 31 19 27 10 26 14 
最大元素： 44

# 最大堆构造算法的 Python 代码
class MaxHeap:
    def __init__(self):
        self.heap = []
    def parent(self, i):
        return (i - 1) // 2
    def left_child(self, i):
        return 2 * i + 1
    def right_child(self, i):
        return 2 * i + 2
    #交换堆中两个元素的函数
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    # 函数将以索引 i 为根的子树堆化
    def heapify_down(self, i):
        left = self.left_child(i)
        right = self.right_child(i)
        largest = i
        #检查左节点是否大于根
        if left < len(self.heap) and self.heap[left] >self.heap[largest]:
            largest = left
        # 检查右子节点是否大于目前最大的子节点
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        # 如果最大的不是根，则将根与最大的交换
        if largest != i:
            self.swap(i, largest)
            self.heapify_down(largest)
    def heapify_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
            parent = self.parent(i)
            self.swap(i, parent)
            i = parent
    # 在末尾插入新元素
    def insert(self, value):
        self.heap.append(value)
        # 如果违反了堆属性，则修复它
        self.heapify_up(len(self.heap) - 1)
    # 从堆中提取最大元素的函数
    def extract_max(self):
        if len(self.heap) == 0:
            print("Heap is empty. Cannot extract maximum element.")
            return None
        max_value = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_value
    # 打印堆元素的函数
    def print_heap(self):
        print("Heap elements:", end=" ")
        for value in self.heap:
            print(value, end=" ")
        print()
# 堆的使用示例
heap = MaxHeap()
heap.insert(35)
heap.insert(33)
heap.insert(42)
heap.insert(10)
heap.insert(14)
heap.insert(19)
heap.insert(27)
heap.insert(44)
heap.insert(26)
heap.insert(31)
heap.print_heap()
max_value = heap.extract_max()
print("最大元素：", max_value)

Heap elements: 44 42 35 33 31 19 27 10 26 14 
最大元素： 44s

最大堆删除算法

让我们推导一个从最大堆中删除元素的算法。最大堆（或最小堆）中的删除操作总是在根节点处进行，以移除最大值（或最小值）。

步骤 1 − 删除根节点。
步骤 2 − 将最后一层的最后一个元素移动到根节点。
步骤 3 − 将此子节点的值与其父节点的值进行比较。
步骤 4 − 如果父节点的值小于子节点的值，则交换它们。
步骤 5 − 重复步骤 3 和 4，直到满足堆的性质。

示例

以下是此操作在各种编程语言中的实现 −

//最大堆删除算法的 C 代码
#include <stdio.h>
#include <stdlib.h>
// 表示堆的结构体
typedef struct {
    int* array; // 用于存储堆元素的数组
    int capacity;   // 堆的最大容量
    int size;       // 堆的当前大小
} Heap;
//创建一个新的堆
Heap* createHeap(int capacity)
{
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->array = (int*)malloc(capacity * sizeof(int));
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 交换堆中的两个元素
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 堆化以索引 i 为根的子树
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左节点是否大于根
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的子节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大的不是根，则将根与最大的交换
    if (largest != i) {
        swap(&heap->array[i], &heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        printf("Heap is full. Cannot insert more elements.
");
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;
    // 如果违反了堆属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中删除最大元素
int deleteMax(Heap* heap)
{
    if (heap->size == 0) {
        printf("Heap is empty. Cannot extract maximum element.
");
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 将根堆化
    heapify(heap, 0);
    return max;
}
// 打印堆的元素
void printHeap(Heap* heap)
{
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->array[i]);
    }
    printf("
");
}
// 释放堆占用的内存
void destroyHeap(Heap* heap)
{
    free(heap->array);
    free(heap);
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
	printf("删除前的堆元素： ");
    printHeap(heap);
    // Deleting the maximum element in the heap
    int max = deleteMax(heap);
    printf("最大元素： %d
", max);
	printf("删除后的堆元素： ");
    printHeap(heap);
    destroyHeap(heap);
    return 0;
}

删除前的堆元素： 44 42 35 33 31 19 27 10 26 14 
最大元素： 44
删除后的堆元素： 42 33 35 26 31 19 27 10 14

//最大堆删除算法的 C++ 代码
#include 
// 表示堆的结构体
struct Heap {
    int* array; // 用于存储堆元素的数组
    int capacity;   // 堆的最大容量
    int size;       // 堆的当前大小
};
//创建一个新的堆
Heap* createHeap(int capacity)
{
    Heap* heap = new Heap;
    heap->array = new int[capacity];
    heap->capacity = capacity;
    heap->size = 0;
    return heap;
}
// 交换堆中的两个元素
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
// 堆化以索引 i 为根的子树
void heapify(Heap* heap, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 检查左节点是否大于根
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;
    // 检查右子节点是否大于目前最大的子节点
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;
    // 如果最大的不是根，则将根与最大的交换
    if (largest != i) {
        swap(heap->array[i], heap->array[largest]);
        heapify(heap, largest);
    }
}
// 将新元素插入堆的函数
void insert(Heap* heap, int value)
{
    if (heap->size == heap->capacity) {
        std::cout << "Heap is full. Cannot insert more elements." << std::endl;
        return;
    }
    // 在末尾插入新元素
    int i = heap->size++;
    heap->array[i] = value;

    // 如果违反了堆属性，则修复它
    while (i != 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(heap->array[i], heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
// 从堆中删除最大元素的函数
int deleteMax(Heap* heap)
{
    if (heap->size == 0) {
        std::cout << "Heap is empty. Cannot extract maximum element." << std::endl;
        return -1;
    }
    // 存储根元素
    int max = heap->array[0];
    // 用最后一个元素替换根
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    // 将根堆化
    heapify(heap, 0);

    return max;
}
// 打印堆元素的函数
void printHeap(Heap* heap)
{
    for (int i = 0; i < heap->size; i++) {
        std::cout << heap->array[i] << " ";
    }
    std::cout << std::endl;
}
// 释放堆占用的内存的函数
void destroyHeap(Heap* heap)
{
    delete[] heap->array;
    delete heap;
}
// 堆的使用示例
int main()
{
    Heap* heap = createHeap(10);
    insert(heap, 35);
    insert(heap, 33);
    insert(heap, 42);
    insert(heap, 10);
    insert(heap, 14);
    insert(heap, 19);
    insert(heap, 27);
    insert(heap, 44);
    insert(heap, 26);
    insert(heap, 31);
	std::cout << "删除前的堆元素： ";
    printHeap(heap);
    int max = deleteMax(heap);
    std::cout << "最大元素： " << max << std::endl;
	std::cout << "删除后的堆元素： ";
    printHeap(heap);
    destroyHeap(heap);
    return 0;
}

删除前的堆元素： 44 42 35 33 31 19 27 10 26 14 
最大元素： 44
删除后的堆元素： 42 33 35 26 31 19 27 10 14 

// 最大堆删除算法的 Java 代码
// 表示堆的结构
class Heap {
    private int[] array;  // 用于存储堆元素的数组
    private int capacity;  // 堆的最大容量
    private int size;      // 堆的当前大小
    // 创建新堆
    public Heap(int capacity) {
        this.array = new int[capacity];
        this.capacity = capacity;
        this.size = 0;
    }
    // 交换堆中的两个元素
    private void swap(int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    // 堆化以索引 i 为根的子树
    private void heapify(int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;     
        // 检查左节点是否大于根
        if (left < size && array[left] > array[largest])
            largest = left;         
        // 检查右子节点是否大于目前最大的子节点
        if (right < size && array[right] > array[largest])
            largest = right;
        // 如果最大的不是根，则将根与最大的交换
        if (largest != i) {
            swap(i, largest);
            heapify(largest);
        }
    }
    // Insert a new element into the heap
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full. Cannot insert more elements.");
            return;
        }
        // 在末尾插入新元素
        int i = size++;
        array[i] = value;
        // 如果违反了堆属性，则修复它
        while (i != 0 && array[(i - 1) / 2] < array[i]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
    // 从堆中删除最大元素
    public int deleteMax() {
        if (size == 0) {
            System.out.println("Heap is empty. Cannot extract maximum element.");
            return -1;
        }
        // 存储根元素
        int max = array[0];
        // 用最后一个元素替换根
        array[0] = array[size - 1];
        size--;
        // 将根堆化
        heapify(0);
        return max;
    }
    // 打印堆的元素
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    // 释放堆占用的内存
    public void destroyHeap() {
        array = null;
        size = 0;
    }
}
//插入元素
public class Main {
    public static void main(String[] args) {
        Heap heap = new Heap(10);
        heap.insert(35);
        heap.insert(33);
        heap.insert(42);
        heap.insert(10);
        heap.insert(14);
        heap.insert(19);
        heap.insert(27);
        heap.insert(44);
        heap.insert(26);
        heap.insert(31);
		System.out.print("删除前的堆元素： ");
        heap.printHeap();
        int max = heap.deleteMax();
        System.out.println("最大元素： " + max);  
        //Printing the heap elements after deletion of max element
		System.out.print("删除后的堆元素： ");
        heap.printHeap();
        heap.destroyHeap();
    }
}

删除前的堆元素： 44 42 35 33 31 19 27 10 26 14 
最大元素： 44
删除后的堆元素： 42 33 35 26 31 19 27 10 14 

#最大堆删除算法的Python代码
class Heap:
    def __init__(self, capacity):
        self.array = [0] * capacity  #用于存储堆元素的数组
        self.capacity = capacity  #堆的最大容量
        self.size = 0  #堆的当前大小
    # 交换堆中的两个元素
    def swap(self, a, b):
        self.array[a], self.array[b] = self.array[b], self.array[a]
    # 堆化以索引 i 为根的子树
    def heapify(self, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        # 检查左节点是否大于根
        if left < self.size and self.array[left] > self.array[largest]:
            largest = left
        # 检查右子节点是否大于目前最大的子节点
        if right < self.size and self.array[right] > self.array[largest]:
            largest = right
        # 如果最大的不是根，则将根与最大的交换
        if largest != i:
            self.swap(i, largest)
            self.heapify(largest)
    # 将新元素插入堆中
    def insert(self, value):
        if self.size == self.capacity:
            print("Heap is full. Cannot insert more elements.")
            return
        # 在末尾插入新元素
        i = self.size
        self.size += 1
        self.array[i] = value
        # 如果违反了堆属性，则修复它
        while i != 0 and self.array[(i - 1) // 2] < self.array[i]:
            self.swap(i, (i - 1) // 2)
            i = (i - 1) // 2
    # 从堆中删除最大元素
    def deleteMax(self):
        if self.size == 0:
            print("Heap is empty. Cannot extract maximum element.")
            return -1
        # 存储根元素
        max_value = self.array[0]
        # 将根元素替换为最后一个元素
        self.array[0] = self.array[self.size - 1]
        self.size -= 1
        # 对根元素进行堆化
        self.heapify(0)
        return max_value
    # 打印堆的元素
    def printHeap(self):
        for i in range(self.size):
            print(self.array[i], end=" ")
        print()
    # 释放堆占用的内存
    def destroyHeap(self):
        self.array = []
        self.size = 0
# 堆的使用示例
heap = Heap(10)
heap.insert(35)
heap.insert(33)
heap.insert(42)
heap.insert(10)
heap.insert(14)
heap.insert(19)
heap.insert(27)
heap.insert(44)
heap.insert(26)
heap.insert(31)
print("删除前的堆元素：", end=" ")
heap.printHeap()
max_value = heap.deleteMax()
print("最大元素：", max_value)
print("删除后的堆元素：", end=" ")
heap.printHeap()
heap.destroyHeap()

删除前的堆元素： 44 42 35 33 31 19 27 10 26 14 
最大元素： 44
删除后的堆元素： 42 33 35 26 31 19 27 10 14